F. Make Zero
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a binary string $$$s$$$ that consists of only $$$0$$$ and $$$1$$$. You can choose some substring of the format $$$10..0..01$$$ i.e. choose two non-adjacent indexes $$$i$$$ and $$$j$$$ and $$$(i + 1 \lt j)$$$, such that $$$s_i = 1$$$ and $$$s_j = 1$$$ and $$$s_k = 0$$$ for all $$$i \lt k \lt j$$$, then replace substring $$$s[i \dots j]$$$ with single $$$0$$$.

Your task is to find out if you can make $$$s$$$ is equal to $$$0$$$ after performing the operation any number of times.

Input

The first line contains a single integer $$$t$$$ $$$(1 \le t \le 200)$$$ — the number of test cases.

The each test case contains a string $$$s$$$ $$$(1 \le |s| \le 10^4)$$$ — consists of $$$0$$$ and $$$1$$$.

Output

For each test case, if possible YES, else NO.

Example
Input
6
0
10101
101101
10001101011
1110000111
1100011100111
Output
YES
NO
NO
YES
YES
YES