Problem: 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.

Solution (in JAVA):

Solution:
import java.util.*;

public class Tester {
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        int ttt = input.nextInt();
        input.nextLine();
        for(int testCase = 1; testCase <= ttt; testCase++){
            String n = input.nextLine();
            
            if(isStringSorted(n) || isStringSorted(n.substring(1)) || n.indexOf("11") == -1){
                System.out.println("YES");
            }else{
                String newString = n.substring(n.indexOf("11"));
                if(n.indexOf("00", n.indexOf("11"))>-1){
                    System.out.println("NO");
                }else{
                    System.out.println("YES");
                }
            }
            
            //System.out.println(isStringSorted(n));
            
            
            
            /*1449A
            int n = input.nextInt();
            int k1 = input.nextInt();
            int k2 = input.nextInt();
            int w = input.nextInt();
            int b = input.nextInt();
            
            if((k1  + k2) / 2 >= w && (2 * n - k1 - k2) / 2 >= b){
                System.out.println("YES");
            }else{
                System.out.println("NO");
            }*/
            
            /*int n = input.nextInt();
            ArrayList<Integer> deck = new ArrayList<Integer>();
            for(int i = 0; i < n; i++){
                deck.add(input.nextInt());
            }
            
            ArrayList newDeck = new ArrayList<Integer>();
            while(deck.size() > 0){
                ArrayList<Integer> sortedDeck = new ArrayList<Integer>();
                sortedDeck.addAll(deck);
                
                int bnInd = deck.indexOf(sortedDeck.get(sortedDeck.size() - 1));
                
                while(bnInd < deck.size()){
                    newDeck.add(deck.remove(bnInd));
                }
            }
            for(int i = 0; i < n; i++){
                System.out.print(newDeck.get(i) + " ");
            }
            System.out.println();*/
            
            /*int n = input.nextInt();
            int m = input.nextInt();
            int[] a = new int[n];
            for(int i = 0; i < n; i++){
                a[i] = input.nextInt();
            }
            int[] b = new int[n];
            for(int i = 0; i < n; i++){
                b[i] = input.nextInt();
            }
            int[] c = new int[m];
            for(int i = 0; i < m; i++){
                c[i] = input.nextInt();
            }
            
            boolean done = false;
            for(int i : b){
                if(i == c[m -1]){
                    System.out.println("NO");
                    done = true;
                }
            }
            
            if(!done){
                
            }*/
            
            /*int n = input.nextInt();
            int k = input.nextInt();
            int[] h = new int[n];
            for(int i = 0; i < n; i++){
                h[i] = input.nextInt();
                
            }
            
            int i = 0;
            boolean done = false;
            for(k = k; k > 0; k--){
                i = 0;
                done = false;
                while(i < h.length - 1 && !done){
                    if(h[i] < h[i + 1]){
                        h[i]++;
                        done = true;
                    }
                    i++;
                }
                if(!done){
                    System.out.println(-1);
                    break;
                }
            }
            
            if(done){
                System.out.println(i);
            }*/
            
            /*int sx = input.nextInt();
            int sy = input.nextInt();
            input.nextLine();
            String s = input.nextLine();
            int x = 0;
            int y = 0;
            
            for(int i = 0; i < s.length(); i++){
                if(sx >= 0 && s.substring(i, i + 1).equals("R")){
                    x++;
                }else if(sx < 0 && s.substring(i, i + 1).equals("L")){
                    x--;
                }
                
                if(sy >= 0 && s.substring(i, i + 1).equals("U")){
                    y++;
                }else if(sy < 0 && s.substring(i, i + 1).equals("D")){
                    y--;
                }
            }
            
            if(Math.abs(y) >= Math.abs(sy) && Math.abs(x) >= Math.abs(sx)){
                System.out.println("YES");
            }else{
                System.out.println("NO");
            }*/
            
            /*1473A:
            int n = input.nextInt();
            int d = input.nextInt();
            boolean allBelow = true;
            int min1 = d;
            int min2 = d;
            int[] z = new int[n];
            
            for(int i = 0; i < n; i++){
                int a = input.nextInt();
                z[i] = a;
                if(a > d){
                    allBelow = false;
                }
                if(a < min1){
                    min2 = min1;
                    min1 = a;
                }else if(a < min2){
                    min2 = a;
                }
            }
            if(min1 + min2 <= d || allBelow){
                System.out.println("YES");
            }else{
                System.out.println("NO");
            }*/
            
            /*1472D:
            int n = input.nextInt();
            ArrayList<Long> a = new ArrayList<Long>();
            for(int i = 0; i < n; i++){
                a.add(input.nextLong());
            }
            Collections.sort(a);
            long aScore = 0;
            long bScore = 0;
            boolean aTurn = true;
            for(int i = n - 1; i >= 0; i--){
                if(aTurn && a.get(i) % 2 == 0){
                    aScore += a.get(i);
                }else if(!aTurn && a.get(i) % 2 == 1){
                    bScore += a.get(i);
                }
                aTurn = !aTurn;
            }
            
            if(aScore > bScore){
                System.out.println("Alice");
            }else if(bScore > aScore){
                System.out.println("Bob");
            }else{
                System.out.println("Tie");
            }*/
            
            /*1472C
            int n = input.nextInt();
            int[] a = new int[n];
            int[] x = new int[n];
            for(int i = 0; i < n; i++){
                a[i] = input.nextInt();
                x[i] = a[i];
            }
            
            for(int i = n - 1; i >= 0; i--){
                if(a[i] + i < n){
                    x[i] += x[i + a[i]];
                }
            }
            int c = 0;
            for(int i = 0; i < n; i++){
                if(x[i] > c){
                    c = x[i];
                }
            }
            System.out.println(c);
            */
            
            /*1472B
            int n = input.nextInt();
            int[] a = new int[n];
            int w = 0;
            int ts = 0;
            int os = 0;
            for(int i = 0; i < n; i++){
                a[i] = input.nextInt();
                if(a[i] == 1){
                    os++;
                }else{
                    ts++;
                }
                w += a[i];
            }
            if(w % 2 == 0 && (n % 2 == 0 || (ts % 2 == 1 && os % 2 == 0 && os > 0))){
                System.out.println("YES");
            }else{
                System.out.println("NO");
            }*/
            
            /*1472A:
            int w = input.nextInt();
            int h = input.nextInt();
            int n = input.nextInt();
            int c = 1;
            while(w % 2 == 0){
                w /= 2;
                c *= 2;
            }
            while(h % 2 == 0){
                h /= 2;
                c *= 2;
            }
            if(c >= n){
                System.out.println("YES");
            }else{
                System.out.println("NO");
            }*/
            
            /*String p = input.nextLine();
            ArrayList<Integer> iss2 = new ArrayList<Integer>();
            ArrayList<Integer> iss3 = new ArrayList<Integer>();
            int c = 0;
            for(int i = 0; i < p.length() - 1; i++){
                if(isPalindrome(p.substring(i, i + 2))){
                    iss2.add(i);
                }
                if(i < p.length() - 2 && isPalindrome(p.substring(i, i + 3)) && !(iss2.size() > 0 && iss2.get(iss2.size() - 1) == i)){
                    iss3.add(i);
                }
            }
            
            //System.out.println(iss2 + "\n" + iss3);
            
            for(int i = 0; i < iss2.size(); i++){
                for(int j = 0; j < iss3.size(); j++){
                    if(iss2.get(i) == iss3.get(j) + 2 || iss2.get(i) + 1 == iss3.get(j)){
                        c++;
                        iss2.remove(i);
                        i--;
                        iss3.remove(j);
                        j += iss3.size();
                    }
                }
            }
            
            for(int i = 0; i < iss3.size(); i++){
                for(int j = i + 1; j < iss3.size(); j++){
                    if(iss3.get(i) == iss3.get(j) || iss3.get(i) == iss3.get(j) + 1 || iss3.get(i) == iss3.get(j) + 2 ||
                    iss3.get(i) + 1 == iss3.get(j) || iss3.get(i) + 2 == iss3.get(j) ){
                        c += 2;
                        iss3.remove(j);
                        iss3.remove(i);
                        i--;
                        j+= iss3.size();
                    }
                }
            }
            
            int strL = 0;
            int index = 1;
            int lastVal = 0;
            if(iss2.size() > 0){
                lastVal = iss2.get(0);
                strL++;
            }
            while(index < iss2.size()){
                if(iss2.get(index) - 1 == lastVal){
                    strL++;
                }else{
                    c += Math.ceil((double)(strL) / 2);
                    strL = 1;
                }
                lastVal = iss2.get(index);
                index++;
            }
            //System.out.println("\t" + strL);
            if(iss2.size() > 0){
                c += Math.ceil((double)(strL + 1) / 2);
            }
            
            c += iss3.size();
            
            System.out.println(c);*/

            /*1466A 
            int n = input.nextInt();
            int[] t = new int[n];
            for(int i = 0; i < n; i++){
                t[i] = input.nextInt();
            }
            
            ArrayList<Integer> diff = new ArrayList<Integer>();
            for(int i = 0; i < n; i++){
                for(int j = i + 1; j < n; j++){
                    int d = Math.abs(t[i] - t[j]);
                    if(!diff.contains(d)){
                        diff.add(d);
                    }
                }
            }
            
            System.out.println(diff.size());*/
            
            /*int n = input.nextInt();
            int x = input.nextInt();
            int[] a = new int[n];
            for(int i = 0; i < n; i++){
                a[i] = input.nextInt();
            }*/
            
            /*1455C:
            int x = input.nextInt();
            int y = input.nextInt();
            System.out.println(x - 1 + " " + y);
            */
            
            /* 1455B:
            int x = input.nextInt();
            int c = 0;
            int k = 1;
            int numJumps = 0;
            while(c < x){
                c += k;
                k++;
                numJumps++;
            }
            if(c - x - 1 < k + 1 && c - x - 1 > 0){
                //numJumps;
            }else{
                numJumps += c - x;
            }
            
            System.out.println(numJumps);*/
            
            /*1455A:
            String n = input.nextLine();
            System.out.println(n.length());
            */
            
            /*int n = input.nextInt();
            int[] mins = new int[n];
            ArrayList<Integer> repeats = new ArrayList<Integer>();
            for(int i = 0; i < n; i++){
                mins[i] = input.nextInt();
            }

            Arrays.sort(mins);
            printArr(mins);
            int count = 0;
            int lastNum = -1;
            for(int i = 0; i < n; i++){
                if(lastNum != mins[i]){
                    if(count > 0){
                        repeats.add(count);
                        System.out.print(count + "-" + lastNum + "-->");
                    }
                    lastNum = mins[i];
                    System.out.print(lastNum + ",");
                    count = 0;
                }else{
                    count++;
                }
            }
            System.out.println();
            */
        
            /*1437B
            String s = input.next() + "";
            System.out.println(s);
            int c = 0;
            boolean hitOne = false;
            for(int i = 0; i < s.length(); i++){
                if(!hitOne && s.substring(i, i + 1).equals("1")){
                    hitOne = true;
                }else if(hitOne && s.substring(i, i + 1).equals("1")){
                    c++;
                }else if(hitOne && s.substring(i, i + 1).equals("0")){
                    hitOne = false;
                }
            }
            if(s.length() >= 1 && s.substring(0, 1).equals(s.substring(s.length() - 1)) && s.substring(0, 1).equals("1")){
                c++;
            }
            System.out.println(c);*/
            
            /*1437A 
            
            int l = input.nextInt();
            int r = input.nextInt();
            
            if(r - l < l){
                System.out.println("YES");
            }else{
                System.out.println("NO");
            }*/
            
            /*int n = input.nextInt();
            int[] a = new int[n];
            int mod = 0;
            for(int i = 0; i < n; i++){
                a[i] = 4 * n - mod * 2;
                mod ++;
            }
            
            /*int[] a = new int[n];
            int index = 0;
            for(int i = 4 * n; i >= 4; i--){
                boolean accepted = true;
                for(int j = 0; j < index; j++){
                    if(a[j] % i == 0 || i % a[j] == 0 || gcd(a[j], i) == 1 ){
                        accepted = false;
                        //System.out.println("*" + a[j]+ " " + i);
                    }
//                    System.out.println("**");
                }
                
                if(accepted){
                    a[index] = i;
                    index++;
                }
                
                if(index == n){
                    break;
                }
            }
            
            for(int i = 0; i < a.length; i++){
                System.out.print(a[i] + " ");
            }
            System.out.println();
            */
            
            /*1433D
            
            int n = input.nextInt();
            int[] a = new int[n];
            int firstOther = n;
            
            boolean possible = false;
            for(int i = 0; i < n; i++){
                a[i] = input.nextInt();
                if(!possible && i != 0 && a[i] != a[i - 1]){
                    possible = true;
                    firstOther = i;
                }
            }
            
            if(possible){
                System.out.println("YES");
                int[][] toPrint = new int[n - 1][2];
                int currIndex = 0;
                for(int i = 1; i < n; i++){
                    if(a[i] != a[0]){
                        toPrint[currIndex][0] = 1;
                        toPrint[currIndex][1] = i + 1;
                    }else{
                        toPrint[currIndex][0] = firstOther + 1;
                        toPrint[currIndex][1] = i + 1;
                    }
                    currIndex++;
                }
                for(int i = 0; i < n - 1; i++){
                    System.out.println(toPrint[i][0] + " " + toPrint[i][1]);
                }
            }else{
                System.out.println("NO");
            }*/
            
            /*1433D
            
            int n = input.nextInt();
            ArrayList<Integer> s = new ArrayList<Integer>();
            for(int i = 0; i < n; i++){
                s.add(input.nextInt());
            }
            boolean done = false;
            
            for(int i = 0; i < n; i++){
                ArrayList<Integer> x = new ArrayList<Integer>();
                for(int j = 0; j < n; j++){
                    x.add(s.get(j));
                }
                int rightDiff = 1;
                int leftDiff = 1;
                int checker = x.get(i);
                while( (i - leftDiff >= 0 && x.get(i - leftDiff) < checker) || (i + rightDiff < x.size() && x.get(i + rightDiff) < checker) ){
                    if(i - leftDiff >= 0 && x.get(i - leftDiff) < checker){
                        checker++;
                        leftDiff++;
                    }else if(i + rightDiff < x.size() && x.get(i + rightDiff) < checker){
                        checker++;
                        rightDiff++;
                    }
                }
                if(i - leftDiff < 0 && i + rightDiff >= x.size()){
                    System.out.println(i + 1);
                    done = true;
                    break;
                }
                
            }
            if(!done){
                System.out.println(-1);
            }*/
            
            /*1433B 
           int n = input.nextInt();
           int[] a = new int[n];
           for(int i = 0; i < a.length; i++){
               a[i] = input.nextInt();
           }
           
           boolean pastOne = false;
           int c = 0;
           int cc = 0;
           for(int i = 0; i < a.length; i++){
               if(!pastOne){
                   if(a[i] == 1){
                       pastOne = true;
                   }
               }else{
                   if(a[i] == 0){
                       cc++;
                   }else{
                       c += cc;
                       cc = 0;
                   }
               }
           }
           System.out.println(c);*/
           
            /*1433A
            
            int[] sameNumber = {1,11,111,1111,2,22,222,2222,3,33,333,3333,4,44,444,4444,5,55,555,5555,6,66,666,6666,7,77,777,7777,8,88,888,8888,9,99,999,9999};
            
            int x = input.nextInt();
            int c = 0;
            for(int i = 0; i < sameNumber.length; i++){
                if(x == sameNumber[i]){
                    if(sameNumber[i] < 10){
                    c++;
                }else if(sameNumber[i] < 100){
                    c+=2;
                }else if(sameNumber[i] < 1000){
                    c += 3;
                }else{
                    c += 4;
                }
                    break;
                }
                
                if(sameNumber[i] < 10){
                    c++;
                }else if(sameNumber[i] < 100){
                    c+=2;
                }else if(sameNumber[i] < 1000){
                    c += 3;
                }else{
                    c += 4;
                }
            }
            
            System.out.println(c);*/
            
            /*int n = input.nextInt();
            int[] a = new int[1];
            a[0] = 1;
            int lowestMoves = 0;
            int[] factorTracker = new int[n];
            
            for(int i = 1; i <= n; i++){
                factorTracker[i - 1] = i + (n / i) - 2;
                if(n % i > 0){
                    factorTracker[i - 1]++;
                }
                if(lowestMoves == 0 || factorTracker[i - 1] < lowestMoves){
                    lowestMoves = factorTracker[i - 1];
                }else{
                    break;
                }
            }
            System.out.println(lowestMoves);*/
            
            /*1426B:
            int n = input.nextInt();
            int m = input.nextInt();
            
            boolean solved = false;
            if(m % 2 == 1){
                System.out.println("NO");
                solved = true;
            }
            
            for(int i = 0; i < n; i++){
                int upperLeft = input.nextInt();
                int upperRight = input.nextInt();
                int lowerLeft = input.nextInt();
                int lowerRight = input.nextInt();
                if(upperRight == lowerLeft && !solved){
                    System.out.println("YES");
                    solved = true;
                }
                
            }
            if(!solved){
                System.out.println("NO");
            }*/
            
            /*1426A:
            int n = input.nextInt();
            int x = input.nextInt();
            if(n <= 2){
                System.out.println(1);
            }else{
                n -= 2;
                System.out.println((int)Math.ceil((double)n / x) + 1);
            }*/
            
            /*1419C
            int n = input.nextInt();
            int x = input.nextInt();
            ArrayList<Integer> lowerRatings = new ArrayList<Integer>();
            int sigmaLR = 0;
            ArrayList<Integer> higherRatings = new ArrayList<Integer>();
            int sigmaHR = 0;
            ArrayList<Integer> sameRatings = new ArrayList<Integer>();
            
            for(int i = 0; i < n; i++){
                int r = input.nextInt();
                if(r - x < 0){
                    lowerRatings.add(r - x);
                    sigmaLR += Math.abs(r - x);
                }else if(r - n > 0){
                    higherRatings.add(r - x);
                    sigmaHR += Math.abs(r - x);
                }else{
                    sameRatings.add(r - x);
                }
            }
            if(lowerRatings.size() == 0 && higherRatings.size() == 0){
                System.out.println(0);
            }else if(sigmaHR == sigmaLR || higherRatings.size() + lowerRatings.size() < n){
                System.out.println(1);
            }else{
                System.out.println(2);
            }*/
            
            /*1419B:
            
            long x = Long.valueOf(input.next());
            int currPow = 0;
            long lastArea = 0;
            while(x - ((long)Math.pow(4, currPow)  + 2 * lastArea) >= 0){
                x -= ((long)Math.pow(4, currPow)  + 2 * lastArea);
                lastArea = ((long)Math.pow(4, currPow)  + 2 * lastArea);
                currPow++;
            }
            System.out.println(currPow);
            */
            
            /*1419A:
            
            int n = input.nextInt();
            String num = input.next();
            
            ArrayList<Integer> oddIndexes = new ArrayList<Integer>();
            ArrayList<Integer> evenIndexes = new ArrayList<Integer>();

            for(int i = 1; i <= n; i++){
                if(i % 2 == 1){
                    oddIndexes.add(Integer.valueOf(num.substring(i - 1, i)) % 10);
                }else{
                    evenIndexes.add(Integer.valueOf(num.substring(i - 1, i)) % 10);
                }
            }
            
            while(evenIndexes.size() + oddIndexes.size() > 1){
                boolean tooken = false;
                for(int i = 0; i < oddIndexes.size(); i++){
                    if(oddIndexes.get(i) % 2 == 0){
                        oddIndexes.remove(i);
                        tooken = true;
                        break;
                    }
                }
                for(int i = 0; i < oddIndexes.size() && !tooken; i++){
                    if(oddIndexes.get(i) % 2 == 1){
                        oddIndexes.remove(i);
                        break;
                    }
                }
                if(evenIndexes.size() + oddIndexes.size() > 1){
                    tooken = false;
                    for(int i = 0; i < evenIndexes.size(); i++){
                        if(evenIndexes.get(i) % 2 == 1){
                            evenIndexes.remove(i);
                            tooken = true;
                            break;
                        }
                    }
                    for(int i = 0; i < evenIndexes.size() && !tooken; i++){
                        if(evenIndexes.get(i) % 2 == 0){
                            evenIndexes.remove(i);
                            break;
                        }
                    }
                }
            }
            if(oddIndexes.size() > 0 && oddIndexes.get(0) % 2 == 0 || evenIndexes.size() > 0 && evenIndexes.get(0) % 2 == 0){
                System.out.println(2);
            }else if(oddIndexes.size() > 0 && oddIndexes.get(0) % 2 == 1 || evenIndexes.size() > 0 && evenIndexes.get(0) % 2 == 1){
                System.out.println(1);
            }
            */
        }
        
    }
    
    private static void printArr(int[] arr){
        System.out.print("[");
        for(int i = 0; i < arr.length; i++){
            System.out.print(arr[i]);
            if(i < arr.length - 1){
                System.out.print(", ");
            }
        }
        System.out.println("]");
    }
    
    private static int gcd(int a, int b){
        int s;
        int l;
        
        if(a > b){
            s = b;
            l = a;
        }else{
            s = a;
            l = b;
        }
        int gcd = 1;
        for(int i = 1; i <= s; i++){
            if(s % i == 0 && b % i == 0){
                gcd = i;
            }
        }
        return gcd;
    }
    
    private static boolean isAlternating(String s){
        String lastChar = s.substring(0, 1);
        for(int i = 1; i < s.length(); i++){
            if(!lastChar.equals(s.substring(i, i + 1))){
                return false;
            }
            lastChar = s.substring(i, i + 1);
        }
        return true;
    }
    
    private static boolean isPalindrome(String s){
        for(int i = 0; i < s.length() / 2; i++){
            if(!(s.charAt(i) == s.charAt(s.length() - (i + 1)))){
                return false;
            }
        }
        return true;
    }
    
    private static String findRepString(String str){
        String repStr = str;
        String tempRepStr = str;
        
        /*String repStr = str.substring(0, 1);
        for(int i = 1; i < str.length(); i += repStr.length()){
            System.out.println(repStr + "   " + str.substring(i, i + repStr.length()));
            if(i + repStr.length() <= str.length() && !str.substring(i, i + repStr.length()).equals(repStr)){
                repStr = str.substring(0, i + 1);
            }
        }
        if(repStr.length() > str.length() - repStr.length()){
            repStr = str;
        }*/
        return repStr;
    }
    
    private static ArrayList<Integer> getListOfFactors(int n){
        ArrayList<Integer> a = new ArrayList<Integer>();
        
        
        
        return a;
    }
    
    private static boolean isStringSorted(String s){
        boolean zeros = true;
        int index = 0;
        while(index < s.length()){
            if(zeros){
                if(!s.substring(index, index + 1).equals("0")){
                    zeros = false;
                }
            }else{
                if(!s.substring(index, index + 1).equals("1")){
                    return false;
                }
            }
            index++;
        }
        return true;
    }
}