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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;
public class Main{
    static class FastScanner {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            StringTokenizer st = new StringTokenizer("");

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

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

            int[] nextArray(int n) {
                int[] a = new int[n];
                for (int i = 0; i < n; i++) a[i] = nextInt();
                return a;
            }
            long[] nextArray(long n) {
                long[] a = new long[(int) n];
                for (int i = 0; i < n; i++) a[i] = nextLong();
                return a;
            }

            long nextLong() {
                return Long.parseLong(next());
            }
        }
    static class FastWriter extends PrintWriter {
            FastWriter(){
                super(System.out);
            }
            void println(int[] array) {
                for(int i=0; i<array.length; i++) {
                    print(array[i]+" ");
                }
                println();
            }
            void println(long [] array) {
                for(int i=0; i<array.length; i++) {
                    print(array[i]+" ");
                }
                println();
            }
        }
    static int MOD=1000003;
    public static void main(String[] args) {
        FastScanner in = new FastScanner();
        FastWriter out = new FastWriter();
        int t=1;
        t=in.nextInt();
        while (t-->0){
            String[] str=in.next().split("1");
            int cnt=0;
            for (int i = 0; i < str.length; i++) {
                if(!str[i].equals("")){
                    cnt++;
                }
            }
            if(cnt==0){
                out.println(0);
            }else if(cnt==1){
                out.println(1);
            }else {
                out.println(2);
            }
        }
        out.close();
    }
    static int count(String a, String b) {
        int m = a.length();
        int n = b.length();
        int lookup[][] = new int[m + 1][n + 1];
        for (int i = 0; i <= n; ++i){
            lookup[0][i] = 0;
        }
        for (int i = 0; i <= m; ++i){
            lookup[i][0] = 1;
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (a.charAt(i - 1) == b.charAt(j - 1)){
                    lookup[i][j] = lookup[i - 1][j - 1] + lookup[i - 1][j];
                }else{
                    lookup[i][j] = lookup[i - 1][j];
                }
                if(lookup[i][j]>=1000000007){
                    lookup[i][j]-=1000000007;
                }
            }
        }

        return lookup[m][n];
    }
    static void BFS(ArrayList<Integer>[] adj, int src, int[] dist, int[] paths, int n) {
        boolean[] visited = new boolean[n];
        for (int i = 0; i < n; i++){
            visited[i] = false;
        }
        dist[src] = 0;
        paths[src] = 1;
        Queue<Integer> q = new LinkedList<>();
        q.add(src);
        visited[src] = true;
        while (!q.isEmpty()) {
            int curr = q.peek();
            q.poll();
            for (int x : adj[curr]) {
                if (!visited[x]) {
                    q.add(x);
                    visited[x] = true;
                }
                if (dist[x] > dist[curr] + 1) {
                    dist[x] = dist[curr] + 1;
                    paths[x] = paths[curr];
                } else if (dist[x] == dist[curr] + 1){
                    paths[x] += paths[curr];
                }
                if(paths[x]>=1000000007){
                    paths[x]-=1000000007;
                }
            }
        }
    }
    static void findShortestPaths(ArrayList<Integer>[] adj, int s, int n) {
        int[] dist = new int[n], paths = new int[n];
        for (int i = 0; i < n; i++){
            dist[i] = Integer.MAX_VALUE;
        }
        for (int i = 0; i < n; i++){
            paths[i] = 0;
        }
        BFS(adj, s, dist, paths, n);
        System.out.println((paths[n-1])%1000000007);
    }
    //Arrays.sort(a, (o1, o2) -> (o1[0] - o2[0]));
    static int totalPrimeFactors(int n) {
        int cnt=0;
        while (n%2==0) {
            cnt++;
            n /= 2;
        }
        int num= (int) Math.sqrt(n);
        for (int i = 3; i <= num; i+= 2) {
            while (n%i == 0) {
                cnt++;
                n /= i;
                num=(int)Math.sqrt(n);
            }
        }
        if (n > 2){
            cnt++;
        }
        return cnt;
    }
    static char get(int i){
        return (char)(i+'a');
    }
    static boolean distinct(int num){
        HashSet<Integer> set=new HashSet<>();
        int len=String.valueOf(num).length();
        while (num!=0){
            set.add(num%10);
            num/=10;
        }
        return set.size()==len;
    }
    static int maxSubArraySum(int a[]) {
        int n=a.length,max=a[0],sum=a[0];
        for (int i = 1; i < n; i++) {
            sum=Math.max(sum+a[i],a[i]);
            max=Math.max(max,sum);
        }
        return max;
    }
    static void segmentedSieve(ArrayList<Integer> res,int low, int high) {
        if(low < 2){
            low = 2;
        }
        ArrayList<Integer> prime = new ArrayList<>();
        sS2(high, prime);
        boolean[] mark = new boolean[high - low + 1];
        Arrays.fill(mark, true);
        for (int i = 0; i < prime.size(); i++) {
            int loLim = (low / prime.get(i)) * prime.get(i);
            if (loLim < low){
                loLim += prime.get(i);
            }
            if (loLim == prime.get(i)){
                loLim += prime.get(i);
            }
            for (int j = loLim; j <= high; j += prime.get(i)) {
                mark[j - low] = false;
            }
        }
        for (int i = low; i <= high; i++) {
            if (mark[i - low]){
                System.out.println(i);
                res.add(i);
            }
        }
    }
    static void sS2(int limit, ArrayList<Integer> prime) {
        int bound = (int)Math.sqrt(limit);
        boolean[] mark = new boolean[bound + 1];
        for (int i = 0; i <= bound; i++){
            mark[i] = true;
        }
        for (int i = 2; i * i <= bound; i++) {
            if (mark[i]) {
                for (int j = i * i; j <= bound; j += i){
                    mark[j] = false;
                }
            }
        }
        for (int i = 2; i <= bound; i++) {
            if (mark[i]){
                prime.add(i);
            }
        }
    }
    static boolean[] sieveOfEratosthenes(int n){
        boolean[] prime = new boolean[n + 1];
        Arrays.fill(prime,true);
        prime[0]=false;prime[1]=false;
        for (int p = 2; p * p <= n; p++) {
            if(prime[p]){
                for (int i = p * p; i <= n; i += p){
                    prime[i] = false;
                }
            }
        }
        return prime;
    }
    static int highestPowerOf2(int n) {
        if (n < 1){ return 0; }
        int res = 1;
        for (int i = 0; i < 8 * Integer.BYTES; i++) {
            int curr = 1 << i;
            if (curr > n){ break; }
            res = curr;
        }
        return res;
    }
    static int reduceFraction(int x, int y) {
        int d= gcd(x, y);
        return x/d+y/d;
    }
    static boolean subset(int[] ar,int n,int sum){
        if(sum==0){
            return true;
        }
        if(n<0||sum<0){
            return false;
        }
        return subset(ar,n-1,sum)||subset(ar,n-1,sum-ar[n]);
    }
    static boolean isPrime(int n){
        if(n<=1) return false;
        for(int i = 2;i<=Math.sqrt(n);i++){
            if (n % i == 0) return false;
        }
        return true;
    }
    static int gcd(int a, int b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }
    static long gcd(long a, long b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }
    static long lcm(long a, long b) {
        return (a * b) / gcd(a, b);
    }
    static int lcm(int a, int b) {
        return (a * b) / gcd(a, b);
    }
    static int isPowerOfTwo(long n) {
        int ans=0;
        if(n==0){
            return ans;
        }
        while (n%2==0){
            ans++;
            n/=2;
        }
        return ans;
    }
    static boolean isPerfectSquare(int x){
        if (x >= 0) {
            int sr = (int)Math.sqrt(x);
            return ((sr * sr) == x);
        }
        return false;
    }
    static int lower_bound(int[] arr, int x) {
        int low_limit = 0, high_limit = arr.length, mid;
        while (low_limit < high_limit) {
            mid = (low_limit + high_limit) / 2;
            if (arr[mid] >= x){
                high_limit = mid;
            }else{
                low_limit = mid + 1;
            }
        }
        return low_limit;
    }
    static int upper_bound(int[] arr, int x) {
        int low_limit = 0, high_limit = arr.length, mid;
        while (low_limit < high_limit) {
            mid = (low_limit + high_limit) / 2;
            if (arr[mid] > x){
                high_limit = mid;
            }else{
                low_limit = mid + 1;
            }
        }
        return low_limit;
    }
    static int binarySearch(int[] ar,int n,int num){
        int low=0,high=n-1;
        while (low<=high){
            int mid=(low+high)/2;
            if(ar[mid]==num){
                return mid;
            }else if(ar[mid]>num){
                high=mid-1;
            }else {
                low=mid+1;
            }
        }
        return -1;
    }
    static int fib(int n) {
        long[][] F = new long[][]{{1,1},{1,0}};
        if (n == 0){
            return 0;
        }
        power(F, n-1);
        return (int)F[0][0];
    }
    static void multiply(long F[][], long M[][]) {
        long x =  (F[0][0]*M[0][0])%1000000007 + (F[0][1]*M[1][0])%1000000007;
        long y =  (F[0][0]*M[0][1])%1000000007 + (F[0][1]*M[1][1])%1000000007;
        long z =  (F[1][0]*M[0][0])%1000000007 + (F[1][1]*M[1][0])%1000000007;
        long w =  (F[1][0]*M[0][1])%1000000007 + (F[1][1]*M[1][1])%1000000007;
        F[0][0] = x%1000000007;
        F[0][1] = y%1000000007;
        F[1][0] = z%1000000007;
        F[1][1] = w%1000000007;
    }
    static void power(long F[][], int n) {
        if( n == 0 || n == 1){
            return;
        }
        long M[][] = new long[][]{{1,1},{1,0}};
        power(F, n/2);
        multiply(F, F);
        if (n%2 != 0){
            multiply(F, M);
        }
    }
    static int binaryExponentiation(int x,int n){
        int ans=1;
        while (n>0){
            if(n%2!=0){
                ans=(ans*x)%MOD;
            }
            x=(x*x)%MOD;
            n/=2;
        }
        return ans;
    }
    static void bfs(ArrayList<Integer>[] ar,int node){
        boolean[] visited=new boolean[ar.length];
        Queue<Integer> queue=new LinkedList<>();
        visited[node]=true;
        queue.add(node);
        while(!queue.isEmpty()){
            int nn=queue.poll();
            System.out.print(nn+" ");
            for(int n : ar[nn]) {
                if (!visited[n]) {
                    visited[n] = true;
                    queue.add(n);
                }
            }
        }
        System.out.println();
    }
    static void dfs(ArrayList<Integer>[] ar,int node){
        boolean[] visited=new boolean[ar.length];
        dfsUtil(ar,node,visited);
        System.out.println();
    }
    static void dfsUtil(ArrayList<Integer>[] ar,int node,boolean[] visited){
        visited[node]=true;
        //System.out.print(node+" ");
        for(Integer n:ar[node]){
            if(!visited[n]){
                dfsUtil(ar,n,visited);
            }
        }
    }
}