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.text.DecimalFormat;
import java.util.*;


public class Main {

    public static void main(String[] args) throws IOException {
       Reader.init(System.in);
       BufferedWriter output = new BufferedWriter(new OutputStreamWriter(System.out));
       int t = Reader.nextInt();
       while ( t > 0) {
           char string[] = Reader.next().toCharArray();
           int i = 0;
           boolean allZero = true;
           boolean allOne  = true;
           if ( string[0] == '0'){
               allZero = true;
               allOne = false;
           }
           else{
               allOne = true;
               allZero = false;
           }
           i = 1;
           int b =0 ;
           while ( i < string.length){
               if ( string[i] != string[i-1]){
                 b++;
               }
               i++;
           }
           if ( b == 0){
               if (allOne){
                   System.out.println(0);
               }
               else{
                   System.out.println(1);
               }
           }
           else if ( b== 1){
               System.out.println(1);
           }
           else{
               int ans =2;
               if ( allOne){
                   ans = min(2,b/2);
               }
               System.out.println(ans);
           }
           t--;
       }


    }

    private static boolean calculate(int l,int r,int[] a,int b[]){
        int countA = 0;
        int countB = 0;
        if ( l == 0){
            countA = a[r];
            countB = b[r];
        }
        else{
            countA = a[r] - a[l-1];
            countB = b[r] - b[l-1];
        }
        if ( countA == countB){
            return true;
        }
        else{
            return false;
        }
    }



    private static long calculate(ArrayList<Integer> array,int n){
        int i = 1;
        long count = 0;
        while ( i <= n){
            if ( (i&1) == 1){
                int v = array.remove(0);
                count+= abs(v-i);
            }
            i++;
        }
        return  count;
    }

    private static int bs(int low,int high,int[] array,int find){
        if ( low <= high ){
            int  mid = low + (high-low)/2;
            if ( array[mid] > find){
                high = mid -1;
                return bs(low,high,array,find);
            }
            else if ( array[mid] < find){
                low = mid+1;
                return bs(low,high,array,find);
            }
            return mid;
        }
        return -1;
    }

    private static int max(int a, int b) {
        return  Math.max(a,b);
    }

    private static int min(int a,int b){
        return  Math.min(a,b);
    }

    public static long modularExponentiation(long a,long b,long mod){
        if ( b == 1){
            return a;
        }
        else{
            long ans = modularExponentiation(a,b/2,mod)%mod;
            if ( b%2 == 1){
                return (a*((ans*ans)%mod))%mod;
            }

            return ((ans*ans)%mod);
        }
    }

    public static long sum(long n){
        return  (n*(n+1))/2;
    }
    public static long abs(long a){
        return a < 0 ? (-1*a) : a;
    }
    public static long gcd(long a,long b){
        if ( a == 0){
            return b;
        }
        else{
            return gcd(b%a,a);
        }
    }


}

class Reader {
    static BufferedReader reader;
    static StringTokenizer tokenizer;


    static void init(InputStream input) {
        reader = new BufferedReader(
                new InputStreamReader(input));
        tokenizer = new StringTokenizer("");
    }

    static String next() throws IOException {
        while ( ! tokenizer.hasMoreTokens() ) {

            tokenizer = new StringTokenizer(
                    reader.readLine() );
        }
        return tokenizer.nextToken();
    }

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

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

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

class NComparator implements Comparator<Node>{
    @Override
    public int compare(Node o1, Node o2) {
       if ( o1.value> o2.value){
           return  1;
       }
       else if ( o2.value > o1.value){
           return -1;
       }
       else{
           if ( o1.index < o2.index){
               return  1;
           }
           else if ( o1.index > o2.index){
               return -1;
           }
           else{
               return 0;
           }
       }
    }
}

class Node{
    int value;
    int length;
    int index;

    Node(int v,int l,int i){
        value = v;
        length = l;
        index = i;
    }


}