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.io.*;
import java.util.*;
import java.lang.*;

public class Main {
    static final int MAXN = 100001; // sqrt of 10^9 ;
    static ArrayList<Integer> arr1 =new ArrayList<>();
    static int int_max = Integer.MAX_VALUE;
    static int[] spf = new int[MAXN];

    public static void main(String[] args) throws IOException {
        FastReader sc = new FastReader();
        int t = sc.nextInt();
        while (t-- != 0) {

            /*int[] a =new int[n];
            for(int i=0;i<n;i++) {
                a[i] = sc.nextInt();
            }*/
            String s=sc.nextLine();
            int n =s.length();

            boolean ok=true;
            boolean check=false;

            int index=-1;
            for(int i=0;i<n;i++)
            {
                if (s.charAt(i)=='1')
                    {
                        index=i;
                        break;
                    }

            }
            if(index!=-1)
                ok=solve(s,index);
            if(arr1.size()>1)
                ok=check(arr1);

            arr1.clear();;
            if(ok)
            System.out.println("YES");
            else
                System.out.println("NO");
        }

    }

    private static boolean solve(String s, int index) {
        int n=s.length();
        //if included
        if(index>=n)
            return true;

        ArrayList<Integer> arr=new ArrayList<>();
        boolean ok=true;
        for(int i=index + 1;i<n;i++)
        {
            if (s.charAt(i)=='0')
            {
                arr.add(i);
            }
        }
        ok=check(arr);
        if(ok)
            return true;
        arr.clear();

        //if not included

        arr1.add(index);
        int c=0;
        for(int i=index+1;i<n;i++)
        {
            if (s.charAt(i)=='1')
            {
                c=i;
                break;
            }
        }
        if(c==0)
            return true;
        return solve(s,c);

    }
    public static boolean check(ArrayList<Integer> arr )
    {
        for(int i=0;i<arr.size()-1;i++)
        {
            if(arr.get(i+1) - arr.get(i) <= 1)
                return false;
        }
        return true;
    }

    public static int sol(int y)
    {
        int x = Integer.highestOneBit(y);
        return x;
    }
    public static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new
                    InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }

    public static int[] large(int[] arr) {
        Stack<Integer> s = new Stack<>();
        int nge[] = new int[arr.length];
        for (int i = arr.length - 1; i >= 0; i--) {
            if (!s.empty()) {
                while (!s.empty() && arr[s.peek()] <= arr[i]) {
                    s.pop();
                }
            }
            nge[i] = s.empty() ? -1 : arr[s.peek()];
            s.push(i);
        }

        System.arraycopy(nge, 0, arr, 0, arr.length);

        return arr;
    }

    static long mod_inv(long a, long m) {
        long m0 = m, t, q;
        long x0 = 0, x1 = 1;

        if (m == 1)
            return 0;

        // Apply extended Euclid Algorithm
        while (a > 1) {
            // q is quotient
            q = a / m;

            t = m;

            // m is remainder now, process
            // same as euclid's algo
            m = a % m;
            a = t;

            t = x0;

            x0 = x1 - q * x0;

            x1 = t;
        }

        // Make x1 positive
        if (x1 < 0)
            x1 += m0;

        return x1;
    } //(a*res)%m==1

    static long power(long x, long y) {
        long res = 1;
        while (y > 0) {
            if ((y & 1) == 1)
                res = res * x;

            y = y >> 1; // y = y/2
            x = x * x;
        }
        return res;
    } //return x^y;

    static int fact(int n) {
        int res = 1;
        for (int i = 2; i <= n; i++)
            res = res * i;
        return res;
    }

    static int ceilSearch(int[] arr, int low, int high, int x) {
        int mid;

        if (x <= arr[low])
            return low;
        if (x > arr[high])
            return -1;

        mid = (low + high) / 2;
        if (arr[mid] == x)
            return mid;
        else if (arr[mid] < x) {
            if (mid + 1 <= high && x <= arr[mid + 1])
                return mid + 1;
            else
                return ceilSearch(arr, mid + 1, high, x);
        } else {
            if (mid - 1 >= low && x > arr[mid - 1])
                return mid;
            else
                return ceilSearch(arr, low, mid - 1, x);
        }
    }

    static int floorSearch(int[] arr, int low, int high, int x) {
        // If low and high cross each other
        if (low > high)
            return -1;

        // If last element is smaller than x
        if (x >= arr[high])
            return high;

        // Find the middle point
        int mid = (low + high) / 2;

        // If middle point is floor.
        if (arr[mid] == x)
            return mid;

        // If x lies between mid-1 and mid
        if (
                mid > 0 && arr[mid - 1] <= x && x < arr[mid])
            return mid - 1;

        // If x is smaller than mid, floor
        // must be in left half.
        if (x < arr[mid])
            return floorSearch(
                    arr, low,
                    mid - 1, x);

        // If mid-1 is not floor and x is
        // greater than arr[mid],
        return floorSearch(
                arr, mid + 1, high,
                x);
    }

    static void sieve() {
        spf[1] = 1;
        for (int i = 2; i < MAXN; i++)
            spf[i] = i;
        for (int i = 4; i < MAXN; i += 2)
            spf[i] = 2;

        for (int i = 3; i * i < MAXN; i++) {
            if (spf[i] == i) {
                for (int j = i * i; j < MAXN; j += i)
                    if (spf[j] == j)
                        spf[j] = i;
            }
        }
    } //spf

    static ArrayList<Integer> getFactorization(int x) {
        sieve();
        ArrayList<Integer> ret = new ArrayList<>();
        while (x != 1) {
            ret.add(spf[x]);
            x = x / spf[x];
        }
        return ret;
    }

    static ArrayList<Integer> sieveOfEratosthenes(int n) {
        ArrayList<Integer> arr = new ArrayList<Integer>();
        boolean[] prime = new boolean[n + 1];
        Arrays.fill(prime, true);
        for (int p = 2; p * p <= n; p++) {
            if (prime[p]) {
                for (int i = p * p; i <= n; i += p)
                    prime[i] = false;
            }
        }
        for (int i = 2; i <= n; i++) {
            if (prime[i])
                arr.add(i);
        }
        return arr;
    }

    static boolean isPrime(int n) {
        if (n <= 1) return false;
        if (n <= 3) return true;
        if (n % 2 == 0 || n % 3 == 0) return false;

        for (int i = 5; i * i <= n; i = i + 6)
            if (n % i == 0 || n % (i + 2) == 0)
                return false;

        return true;
    }

    static int funhelpfulforsegmented(int[] primes, int numprimes) {

        primes[numprimes++] = 2;

        for (int i = 3; i <= 32000; i += 2) {
            boolean isprime = true;
            double cap = Math.sqrt(i) + 1.0;

            for (int j = 0; j < numprimes; j++) {
                if (j >= cap) break;
                if (i % primes[j] == 0) {
                    isprime = false;
                    break;
                }
            }
            if (isprime) primes[numprimes++] = i;
        }
        return numprimes;
    }

    static ArrayList<Integer> segmentedsieve(int M, int N) {
        int[] primes = new int[4000];
        int numprimes = 0;
        numprimes = funhelpfulforsegmented(primes, numprimes);
        ArrayList<Integer> arr = new ArrayList<>();
        if (M < 2) M = 2;
        boolean[] isprime = new boolean[100001];
        for (int j = 0; j < 100001; j++) {
            isprime[j] = true;
        }

        for (int i = 0; i < numprimes; i++) {
            int p = primes[i];
            int start;

            if (p >= M) start = p * 2;
            else start = M + ((p - M % p) % p);

            for (int j = start; j <= N; j += p) {
                isprime[j - M] = false;
            }
        }
        for (int i = M; i <= N; i++) {
            if (isprime[i - M]) arr.add(i);
        }
        return arr;
    }

    static long gcd(long a, long b) {
        if (a == 0)
            return b;
        return gcd(b % a, a);
    }

    public static int gcdExtended(int a, int b, int x, int y) {
        if (a == 0) {
            x = 0;
            y = 1;
            return b;
        }

        int x1 = 1, y1 = 1;
        int gcd = gcdExtended(b % a, a, x1, y1);
        x = y1 - (b / a) * x1;
        y = x1;
        return gcd;
    } // ax + by = gcd(a,b) ;
    // int gcd of a nd b is gcdExtended(a, b, x, y);

    static long lcm(long a, long b) {
        return (a / gcd(a, b)) * b;
    }

    static void prime_upto_10pow8() {
        boolean[] prime = new boolean[100000000];
        Arrays.fill(prime, true);
        int i;
        prime[1] = false;
        prime[0] = false;
        for (i = 4; i < 100000000; i += 2)
            prime[i] = false;

        prime[2] = true;
        for (i = 3; i * i < 100000000; i += 2) {
            if (prime[i])
                for (int j = i * i; j > 0 && j < 100000000; j = j + (2 * i))
                    prime[j] = false;
        }
        int[] arr = new int[8000000];
        int j = 0;
        arr[0] = 2;
        int n = 100000000;
        for (i = 3; i <= n; i += 2) {
            if (prime[i])
                arr[++j] = i;
        }
        for (i = 1; i <= j; i += 100) {
            System.out.println(arr[i - 1]);
        }
    }



}