A binary string is a string that consists of characters 0 and 1.

Let \operatorname{MEX} of a binary string be the smallest digit among 0, 1, or 2 that does not occur in the string. For example, \operatorname{MEX} of 001011 is 2, because 0 and 1 occur in the string at least once, \operatorname{MEX} of 1111 is 0, because 0 and 2 do not occur in the string and 0 < 2.

A binary string s is given. You should cut it into any number of substrings such that each character is in exactly one substring. It is possible to cut the string into a single substring — the whole string.

A string a is a substring of a string b if a can be obtained from b by deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.

What is the minimal sum of \operatorname{MEX} of all substrings pieces can be?

Input

The input consists of multiple test cases. The first line contains a single integer t (1 ≤ t ≤ 10^4) — the number of test cases. Description of the test cases follows.

Each test case contains a single binary string s (1 ≤ |s| ≤ 10^5).

It's guaranteed that the sum of lengths of s over all test cases does not exceed 10^5.

Output

For each test case print a single integer — the minimal sum of \operatorname{MEX} of all substrings that it is possible to get by cutting s optimally.

Example

Input


6
01
1111
01100
101
0000
01010


Output


1
0
2
1
1
2

Note

In the first test case the minimal sum is \operatorname{MEX}(0) + \operatorname{MEX}(1) = 1 + 0 = 1.

In the second test case the minimal sum is \operatorname{MEX}(1111) = 0.

In the third test case the minimal sum is \operatorname{MEX}(01100) = 2.

import java.io.*;
import java.util.*;

public class Solution {

    /* -------------------------------------- Main Start ----------------------------------- */
    public static void main(String[] args) throws IOException {
        FastReader fs = new FastReader();
        StringBuilder sb = new StringBuilder();
        int t = Integer.parseInt(fs.nextLine().trim());
        while (t-- > 0) {
            char[] str = fs.nextLine().toCharArray();
            ArrayList<Character> zero = new ArrayList<>();
            char s = str[0];
            int temZ = 0, temO = 0;
            if (str[0] == '0') {
                temZ++;
            } else {
                temO++;
            }
            for (int i = 1; i < str.length; i++) {
                if (str[i] == '0') {
                    temZ++;
                } else {
                    temO++;
                }
                if (s != str[i]) {
                    zero.add(s);
                    s = str[i];
                }
            }
            if (zero.size() == 0 || s != zero.get(zero.size() - 1)) {
                zero.add(s);
            }
            int min = 0;
            for (int i = 0; i < zero.size(); i++) {
                if (zero.get(i) == '0') {
                    min++;
                }
            }
            int curr = 2;
            if (temZ == 0) {
                curr = 0;
            } else if (temO == 0) {
                curr = 1;
            }
            System.out.println(Math.min(min, curr));
        }
    }

    /* ---------------------------------------------------------------------------------------------------------------------------------------------------------------------- 
  
      StringBuilder sb = new StringBuilder();
      sb.append(x + "\n");
    
      Collections.sort(arr, (a, b) -> Integer.compare(a[0], b[0]))
      arr.toArray(new int[arr.size()][])
    
     */
    private static final int MOD_1 = 1000000000 + 7;

    static class FastReader {

        BufferedReader br;
        StringTokenizer st;

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

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

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

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

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

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

        /* --------------------------------------------------------------------------------------------------------------------------------------------------------------------- */
        void printArray(int[] arr) {
            System.out.println(Arrays.toString(arr));
        }

        void printArray(String[] arr) {
            System.out.println(Arrays.toString(arr));
        }

        void printArray(long[] arr) {
            System.out.println(Arrays.toString(arr));
        }

        void print(int data) {
            System.out.println(data);
        }

        void print(String data) {
            System.out.println(data);
        }

        void print(long data) {
            System.out.println(data);
        }

        int[] II(int n) throws IOException {
            int[] d = new int[n];
            String[] arr = nextLine().split(" ");
            for (int i = 0; i < n; i++) {
                d[i] = Integer.parseInt(arr[i]);
            }

            return d;
        }

        String[] IS(int n) throws IOException {
            return nextLine().split(" ");
        }

        long[] IL(int n) throws IOException {
            long[] d = new long[n];
            String[] arr = nextLine().split(" ");
            for (int i = 0; i < n; i++) {
                d[i] = Long.parseLong(arr[i]);
            }
            return d;
        }

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

        public long power(long x, long y, long p) {
            long res = 1;
            x = x % p;
            if (x == 0) {
                return 0;
            }

            while (y > 0) {
                if ((y & 1) == 1) {
                    res = (res * x) % p;
                }
                y = y >> 1;
                x = (x * x) % p;
            }
            return res;
        }

        void sieveOfEratosthenes(boolean prime[], int size) {
            Arrays.fill(prime, true);
            prime[0] = prime[1] = false;
            prime[2] = true;

            for (int p = 2; p * p < size; p++) {
                if (prime[p] == true) {
                    for (int i = p * p; i < size; i += p) {
                        prime[i] = false;
                    }
                }
            }
        }

        public long fact(long n) {
            long ans = 1;
            for (int i = 2; i <= n; i++) {
                ans = (ans * i) % MOD_1;
            }
            return ans;
        }

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

        public int log2(int N) {
            int result = (int) (Math.log(N) / Math.log(2));
            return result;
        }

        // find first element in the arr that is equal to the x. 
        // If x is not present in arr then it will return first element that is greater than x
        // It return arr.size() if all element are smaller than x
        public int lowerBound(int[] arr, int x) {
            int low = 0, high = arr.length, mid = -1;

            while (low < high) {
                mid = (low + high) / 2;

                if (arr[mid] >= x) {
                    high = mid;
                } else {
                    low = mid + 1;
                }
            }

            return low;
        }

        // find first element in the arr that is greater than x. 
        // It return arr.size() if all element are smaller than x
        public int upperBound(int[] arr, int x) {
            int low = 0, high = arr.length, mid = -1;

            while (low < high) {
                mid = (low + high) / 2;

                if (arr[mid] > x) {
                    high = mid;
                } else {
                    low = mid + 1;
                }
            }

            return low;
        }

    }

}
