1499_B. Binary Removals_28598
You are given a string s, consisting only of characters '0' or '1'. Let |s| be the length of s.

You are asked to choose some integer k (k > 0) and find a sequence a of length k such that: 

  * 1 ≤ a_1 < a_2 < ... < a_k ≤ |s|; 
  * a_{i-1} + 1 < a_i for all i from 2 to k. 



The characters at positions a_1, a_2, ..., a_k are removed, the remaining characters are concatenated without changing the order. So, in other words, the positions in the sequence a should not be adjacent.

Let the resulting string be s'. s' is called sorted if for all i from 2 to |s'| s'_{i-1} ≤ s'_i.

Does there exist such a sequence a that the resulting string s' is sorted?

Input

The first line contains a single integer t (1 ≤ t ≤ 1000) — the number of testcases.

Then the descriptions of t testcases follow.

The only line of each testcase contains a string s (2 ≤ |s| ≤ 100). Each character is either '0' or '1'.

Output

For each testcase print "YES" if there exists a sequence a such that removing the characters at positions a_1, a_2, ..., a_k and concatenating the parts without changing the order produces a sorted string.

Otherwise, print "NO".

You may print every letter in any case you want (so, for example, the strings yEs, yes, Yes and YES are all recognized as positive answer).

Example

Input


5
10101011011
0000
11111
110
1100


Output


YES
YES
YES
YES
NO

Note

In the first testcase you can choose a sequence a=[1,3,6,9]. Removing the underlined letters from "10101011011" will produce a string "0011111", which is sorted.

In the second and the third testcases the sequences are already sorted.

In the fourth testcase you can choose a sequence a=[3]. s'= "11", which is sorted.

In the fifth testcase there is no way to choose a sequence a such that s' is sorted.
for q in range(int(input())):
    n=input()
    s=0
    s1=0
    p=0
    l=len(n)
    for i in range(l-1,0,-1):
        if(n[i]=='0' and n[i-1]=='0' ):
            s=1
            p=i-1
            break
    for i in range(p,0,-1):
        if(n[i]=='1' and n[i-1]=='1'):
            s1=1
            break
    
    if(s1==1):
        print("NO")
    else:
        print("YES")
5
10101011011
0000
11111
110
1100
 9
11
11
11
11
11
11
11
11
11
 1
0000011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111100
 1
0000011111111111111111111111111111111111111111111111111111111111111111101111111111111111111111111100
 5
10101011011
1000
11111
110
1100
 5
10101011011
1000
11111
110
0100
 5
10101011001
1000
11111
110
0101
 5
10101011001
1001
11111
110
1100
 5
10101011011
0011
11000
101
1100
 5
10010011011
1011
11100
111
1010
 5
10000011000
1011
11001
111
1000
 1
0000011111111111111111111011111111111111111111111111111111111111111111101111111111111111111111111100
 1
0000011111111111111111011011111111111111111111111111111111111111111111101111111111111111111111111100
 5
10101011011
1000
11111
110
0101
 1
0000011111011111111111011011111111111111111111111111111111111111111111101111111111111111111111111100
 1
0000011111011111111111011011111111111111011111111111111111111111111111101111111111111111111111111100
 5
10101011001
1000
11111
110
0100
 1
0000011111011111111111011011111111111111011111111111111111111111111101101111111111111111111111111100
 5
10101011001
1001
11111
110
0100
 1
0000011111011111111111011011111111111111011111111111111111111111111101101111111111111111101111111100
 1
0000011111011111111111011011111111111110011111111111111111111111111101101111111111111111101111111100
 5
10101011001
1001
11111
110
1110
 1
0000011111011111111111011011111111111110011111111111101111111111111101101111111111111111101111111100
 5
10101011001
1101
11111
110
1110
 1
0000011111011111111111001011111111111110011111111111101111111111111101101111111111111111101111111100
 5
10101011001
1101
11111
111
1110
 1
0000011111011111111111001011111111111110011111111111101111111111111101101111111111111110101111111100
 5
10101011011
1101
11111
111
1110
 1
0000011111011111111111001011111111111110011111111111101111111111111101001111111111111110101111111100
 5
10101011011
1001
11111
111
1110
 1
0010011111011111111111001011111111111110011111111111101111111111111101001111111111111110101111111100
 5
10101011011
1011
11111
111
1110
 1
0010011111011111111111001011111111111111011111111111101111111111111101001111111111111110101111111100
 5
10101011011
1011
11111
110
1110
 1
0010011111011111111111001011111111111111011111111111101111111111111101001111111111111110001111111100
 5
10101011011
1011
11110
110
1110
 1
0010011111011111111111000011111111111111011111111111101111111111111101001111111111111110001111111100
 5
10101011011
1011
11110
111
1110
 1
0010011111011111111111000011011111111111011111111111101111111111111101001111111111111110001111111100
 5
10101011011
1011
11010
111
1110
 1
0010011111011111111111000011011111111111011111111111101101111111111101001111111111111110001111111100
 5
10101011011
1011
11010
111
1100
 1
0010011111011111111111000011011111111111010111111111101101111111111101001111111111111110001111111100
 5
10101011011
1011
11010
101
1100
 1
0010011111011111111111000011011111111111010111110111101101111111111101001111111111111110001111111100
 5
10101011011
0011
11010
101
1100
 1
0010011111011101111111000011011111111111010111110111101101111111111101001111111111111110001111111100
 1
0010011101011101111111000011011111111111010111110111101101111111111101001111111111111110001111111100
 5
00101011011
0011
11000
101
1100
 1
0010011101011101111111000011011111111111000111110111101101111111111101001111111111111110001111111100
 5
00101011011
0011
11010
101
1100
 1
0010011101011101110111000011011111111111000111110111101101111111111101001111111111111110001111111100
 5
00101011011
0011
11010
101
1101
 1
0010001101011101110111000011011111111111000111110111101101111111111101001111111111111110001111111100
 5
00111011011
0011
11010
101
1101
 1
0010001101011101110111100011011111111111000111110111101101111111111101001111111111111110001111111100
 5
00111011011
0011
11010
101
1111
 1
0010001101011101110111100011011111111111000111110111101101111111111100001111111111111110001111111100
 5
00111011011
0011
11010
101
1110
 1
1010001101011101110111100011011111111111000111110111101101111111111100001111111111111110001111111100
 5
00110011011
0011
11010
101
1110
 1
1010001101011101110111100011011111111111000111110111101101011111111100001111111111111110001111111100
 5
00110011011
0011
11010
001
1110
 1
1010001101011101110111100011011111111111000111110111101101011111111100000111111111111110001111111100
 5
00110011011
0001
11010
001
1110
 1
1010001101011101110111100011011111111111000111110111101101011111111100000011111111111110001111111100
 5
00110011011
0000
11010
001
1110
 1
1010001101011101110111100011011111111111000111110111101001011111111100000011111111111110001111111100
 5
00110011011
0000
11110
001
1110
 1
1010001101011101110111100011011111111111001111110111101001011111111100000011111111111110001111111100
 5
00110011011
0000
11110
011
1110
 1
1010001101011101110111100011011111111111001111110111101001011111111100000011111101111110001111111100
 5
00110011011
0000
11110
011
0110
 1
1010001101011101110111100011011111111110001111110111101001011111111100000011111101111110001111111100
 5
00110011011
0100
11110
011
0110
 1
1010001101011101110111100011011111111110001111110111101011011111111100000011111101111110001111111100
 5
10110011011
0100
11110
011
0110
 1
1010001101011101110111100011011111111110001111110111101011011111111100000111111101111110001111111100
 5
10110011011
0100
11110
001
0110
 1
1010001101011101110111100011011111111110001111110111101011111111111100000111111101111110001111111100
 5
11110011011
0100
11110
001
0110
 1
1010001101011101110111100011011101111110001111110111101011111111111100000111111101111110001111111100
 5
11110011011
0100
11010
001
0110
 1
1010001101011101110111100011011101111110001111110111101011111111111100000111111101101110001111111100
 5
11010011011
0100
11010
001
0110
 1
1010001101011101110111100011011101111110001111110111101011111111111100010111111101101110001111111100
 5
11010011111
0100
11010
001
0110
 1
1010001101011101110111100011011101111110001111110111101011111111111100010110111101101110001111111100
 5
11010011111
0100
11010
001
1110
 1
1010001101011101110111100011011101111110001111110111101011111111111100010110111101101110101111111100
 5
11010011111
0100
10010
001
1110
 1
1010001101011101110111100011011101111110001111110111101011111111111100010110111101101010101111111100
 5
11010011111
0100
10000
001
1110
 1
1010001101011101110111100011011101111110001111111111101011111111111100010110111101101010101111111100
 5
11010011111
0100
10000
001
1111
 1
1010001101011101110111100011011101111111001111111111101011111111111100010110111101101010101111111100
 5
11010011111
0100
10100
001
1111
 1
1010001101011101110111100011011101110111001111111111101011111111111100010110111101101010101111111100
 5
11010011111
0101
10100
001
1111
 1
1010001101011101110111100011011101110111001111111111101011111111111100110110111101101010101111111100
 5
11010011111
0101
10110
001
1111
 1
1010001101011101010111100011011101110111001111111111101011111111111100110110111101101010101111111100
 5
11010011011
0101
10110
001
1111
 1
1010001101011101010111100011011101110111001111111111101011111111111100111110111101101010101111111100
 5
11010011011
0101
10110
011
1111
 1
1010001101011101010111100011011101110111001111111111111011111111111100111110111101101010101111111100
 5
11010011011
0101
10100
011
1111
 1
1010001101011101010111100011011101110111001111111111111011111111111110111110111101101010101111111100
 5
11010011011
0101
10100
011
0111
 1
1010001101011101010111100011011101110111001111111111110011111111111110111110111101101010101111111100
 5
11010011011
0101
10100
011
0110
 1
1010001101011101010111100001011101110111001111111111110011111111111110111110111101101010101111111100
 5
11010011011
0101
10100
111
0110
 1
1010001101011101010111100001011101110111001110111111110011111111111110111110111101101010101111111100
 5
11010011011
0111
10100
111
0110
 1
1010001101011101010111100001011101110111001110111111110011111111110110111110111101101010101111111100
 5
11010011011
1111
10100
111
0110
 1
0010001101011101010111100001011101110111001110111111110011111111110110111110111101101010101111111100
 5
10010011011
1111
10100
111
0110
 1
0010001101011101010111100011011101110111001110111111110011111111110110111110111101101010101111111100
 5
10010011011
1111
10100
111
1110
 1
0010001101011101010111100011011101110111001110111111110011111111110110111110111100101010101111111100
 5
10010011011
1011
10100
111
1110
 1
0010001101011101010011100011011101110111001110111111110011111111110110111110111100101010101111111100
 5
10010011011
1011
10100
111
1010
 1
0010001101011101010011100011011101110111001110111111110011111111110110111110101100101010101111111100
 1
0010001101011101010011100010011101110111001110111111110011111111110110111110101100101010101111111100
 5
10010011011
1011
11100
011
1010
 1
0010001101011101010011100110011101110111001110111111110011111111110110111110101100101010101111111100
 5
10010011011
1011
11100
010
1010
 1
0010001101011101010011100110011101110111001110111111110011111111110110111110101100101010101111111000
 5
10010011011
1011
11100
000
1010
 1
0010001101011101010011100110011101110110001110111111110011111111110110111110101100101010101111111000
 5
10010011011
1011
11100
100
1010
 1
0010001101011101010011100110011101110110001110111111110011111011110110111110101100101010101111111000
 5
10010011011
1011
11100
100
0010
 1
0010001101011101010011100110011101110110001110111111111011111011110110111110101100101010101111111000
 5
10000011011
1011
11100
100
0010
 1
0010001101011101010011100110011101110110001110111111111011111011110110111110101100101011101111111000
 5
10000011010
1011
11100
100
0010
 1
0010001100011101010011100110011101110110001110111111111011111011110110111110101100101011101111111000
 5
10000011010
1011
11100
100
0011
 1
0010001100011101010011100110011101110110001110111111111011111011110111111110101100101011101111111000
 5
10000011010
1011
11101
100
0011
 1
0010001100011101010011100110011101110110001110111111111011111011110111111110101100101011101111111001
 5
10000011010
1011
11101
101
0011
 1
0010001100010101010011100110011101110110001110111111111011111011110111111110101100101011101111111001
 5
10000011010
0011
11101
101
0011
 1
0010001100010101010011100110011101110110001110111111111011111011110111111110101100101011101101111001
 5
10000011000
0011
11101
101
0011
 1
0010001100010101010011100110011101110110001110111111111011111011110111111110101100101011101101110001
 5
10000011000
0011
11101
101
0001
 1
0010001100010101010011100110011101110110001110111111111011111011110111111110101100001011101101110001
 5
10000011000
0011
11101
111
0001
 1
0010001100010101010011100110011101110110001110111111111011111011110111110110101100001011101101110001
 5
10000011010
0011
11101
111
0001
 1
0010001100010101010011100110011101110110000110111111111011111011110111110110101100001011101101110001
 5
10000011010
0011
11101
111
0000
 1
0010001100010101010011100110011101111110000110111111111011111011110111110110101100001011101101110001
 5
10000011000
0011
11101
111
0000
 1
0010001100010101010011100110011101111110000110111111111011111001110111110110101100001011101101110001
 5
10000011000
0011
11101
111
1000
 1
0010001100010101010011100110011101111110001110111111111011111001110111110110101100001011101101110001
 5
10000011000
1011
11101
111
1000
 1
0010001100010101010011100110011101111110001110111111111011111001110110110110101100001011101101110001
 5
10000011010
1011
11101
111
1000
 1
0010001100010101010011100110111101111110001110111111111011111001110110110110101100001011101101110001
 1
0010001100010101010011100110111101111110001110111111111011111001110110110110101101001011101101110001
 5
10000011000
1011
11001
101
1000
 1
0010001100010101010011100110111101111110001110111111111011111001110110110110101101000011101101110001
 5
10000011000
1011
10001
101
1000
 1
0010001100010101010011100110111101111110001110111111111001111001110110110110101101000011101101110001
 5
10000011000
1011
10011
101
1000
 1
0011001100010101010011100110111101111110001110111111111001111001110110110110101101000011101101110001
 5
11000011000
1011
10011
101
1000
 1
0011001100010101010011100110111101111110001110111111111001011001110110110110101101000011101101110001
 5
11000011000
1011
00011
101
1000
 1
0011001100010101010011100110111101011110001110111111111001011001110110110110101101000011101101110001
 5
11000011000
1011
00011
001
1000
 1
0011001100010101010011100110111101011110001110111111011001011001110110110110101101000011101101110001
 5
11000011000
1011
00011
000
1000
 1
0011001100010101010011100110111101011110001110111111011001011001110110110110101001000011101101110001
 5
11000011100
1011
00011
000
1000
 1
0011001100010101010011100110111101011110001110101111011001011001110110110110101001000011101101110001
 5
11000011100
1001
00011
000
1000
 1
0011001100010101010011100110111101011110001110101111011001011101110110110110101001000011101101110001
 5
11000011100
0001
00011
000
1000
 1
0011001100010101010011100110111111011110001110101111011001011101110110110110101001000011101101110001
 5
11000011110
0001
00011
000
1000
 1
0011001100010101010011100110111111011010001110101111011001011101110110110110101001000011101101110001
 5
11000011110
0001
00011
000
1001
 1
0011001100010101010011100110111111011010001110001111011001011101110110110110101001000011101101110001
 5
11000011110
0001
00011
001
1001
 1
0011001100010101010011100110111111001010001110001111011001011101110110110110101001000011101101110001
 5
11000011110
0001
00011
000
1101
 1
0011001100010101010011100110111111001010001110001111011001011101110110110110101101000011101101110001
 5
11000011110
0001
00011
000
0101
 1
0011001100010101010011100110111111001010001110001111011001011101110110110110101100000011101101110001
 5
11000011110
0001
00011
000
0001
 1
0011001100010100010011100110111111001010001110001111011001011101110110110110101100000011101101110001
 5
11000011110
0001
00001
000
0001
 1
0011001100010100010011100110111111001010001111001111011001011101110110110110101100000011101101110001
 5
11000011110
0011
00001
000
0001


YES
YES
YES
YES
NO
 YES
YES
YES
YES
YES
YES
YES
YES
YES
 NO
 NO
 YES
YES
YES
YES
NO
 YES
YES
YES
YES
YES
 NO
YES
YES
YES
YES
 NO
YES
YES
YES
NO
 YES
YES
NO
YES
NO
 YES
YES
NO
YES
YES
 NO
YES
NO
YES
YES
 NO
 NO
 YES
YES
YES
YES
YES
 NO
 NO
 NO
YES
YES
YES
YES
 NO
 NO
YES
YES
YES
YES
 NO
 NO
 NO
YES
YES
YES
YES
 NO
 NO
YES
YES
YES
YES
 NO
 NO
YES
YES
YES
YES
 NO
 YES
YES
YES
YES
YES
 NO
 YES
YES
YES
YES
YES
 NO
 YES
YES
YES
YES
YES
 NO
 YES
YES
YES
YES
YES
 NO
 YES
YES
YES
YES
YES
 NO
 YES
YES
YES
YES
YES
 NO
 YES
YES
YES
YES
YES
 NO
 YES
YES
YES
YES
NO
 NO
 YES
YES
YES
YES
NO
 NO
 YES
YES
YES
YES
NO
 NO
 NO
 YES
YES
NO
YES
NO
 NO
 YES
YES
YES
YES
NO
 NO
 YES
YES
YES
YES
YES
 NO
 YES
YES
YES
YES
YES
 NO
 YES
YES
YES
YES
YES
 NO
 YES
YES
YES
YES
YES
 NO
 NO
YES
YES
YES
YES
 NO
 NO
YES
YES
YES
YES
 NO
 NO
YES
YES
YES
YES
 NO
 NO
YES
YES
YES
YES
 NO
 NO
YES
YES
YES
YES
 NO
 NO
YES
YES
YES
YES
 NO
 NO
YES
YES
YES
YES
 NO
 NO
YES
YES
YES
YES
 NO
 NO
YES
YES
YES
YES
 NO
 NO
YES
YES
YES
YES
 NO
 NO
YES
YES
YES
YES
 NO
 NO
YES
YES
YES
YES
 NO
 NO
YES
YES
YES
YES
 NO
 NO
YES
YES
YES
YES
 NO
 NO
YES
YES
YES
YES
 NO
 NO
YES
YES
YES
YES
 NO
 NO
YES
YES
YES
YES
 NO
 NO
YES
YES
YES
YES
 NO
 NO
YES
YES
YES
YES
 NO
 NO
YES
YES
YES
YES
 NO
 NO
YES
YES
YES
YES
 NO
 NO
YES
YES
YES
YES
 NO
 NO
YES
YES
YES
YES
 NO
 NO
YES
YES
YES
YES
 NO
 NO
YES
YES
YES
YES
 NO
 NO
YES
YES
YES
YES
 NO
 NO
YES
YES
YES
YES
 NO
 NO
YES
YES
YES
YES
 NO
 NO
YES
YES
YES
YES
 NO
 YES
YES
YES
YES
YES
 NO
 YES
YES
YES
YES
YES
 NO
 YES
YES
YES
YES
YES
 NO
 YES
YES
YES
YES
YES
 NO
 NO
 YES
YES
NO
YES
YES
 NO
 YES
YES
NO
YES
YES
 NO
 YES
YES
NO
YES
YES
 NO
 YES
YES
NO
YES
YES
 NO
 YES
YES
NO
YES
YES
 NO
 YES
YES
NO
YES
YES
 NO
 YES
YES
NO
YES
YES
 NO
 YES
YES
NO
YES
YES
 NO
 YES
YES
YES
YES
YES
 NO
 YES
YES
YES
YES
YES
 NO
 YES
YES
YES
YES
YES
 NO
 NO
YES
YES
YES
YES
 NO
 NO
YES
YES
YES
YES
 NO
 NO
YES
YES
YES
YES
 NO
 YES
YES
YES
YES
YES
 NO
 YES
YES
YES
YES
YES
 NO
 NO
YES
YES
YES
YES
 NO
 NO
YES
YES
YES
YES
 NO
 NO
YES
YES
YES
YES
 NO
 YES
YES
YES
YES
YES
 NO
 NO
 NO
YES
NO
YES
YES
 NO
 NO
YES
YES
YES
YES
 NO
 NO
YES
YES
YES
YES
 NO
 NO
YES
YES
YES
YES
 NO
 NO
YES
YES
YES
YES
 NO
 NO
YES
YES
YES
YES
 NO
 NO
YES
YES
YES
YES
 NO
 NO
YES
YES
YES
YES
 NO
 NO
YES
YES
YES
YES
 NO
 NO
YES
YES
YES
YES
 NO
 NO
YES
YES
YES
YES
 NO
 NO
YES
YES
YES
YES
 NO
 NO
YES
YES
YES
YES
 NO
 NO
YES
YES
YES
YES
 NO
 NO
YES
YES
YES
YES
 NO
 NO
YES
YES
YES
YES
 NO
 NO
YES
YES
YES
YES
 NO
 NO
YES
YES
YES
YES
