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.
/*
    Author : Akshat Jindal
    from NIT Jalandhar , Punjab , India
    JAI MATA DI
 */
import java.util.*;

import java.io.*;
import java.math.*;
import java.sql.Array;



public class Main {
	  static class FR{
		  
			BufferedReader br;
			StringTokenizer st;
			public FR() {
				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; 
		    } 
		}
	 
	  static long mod = (long)(1e9 + 7);
	 
	static void sort(long[] arr ) {
		 ArrayList<Long> al = new ArrayList<>();
		 for(long e:arr) al.add(e);
		 Collections.sort(al);
		 for(int i = 0 ; i<al.size(); i++) arr[i] = al.get(i);
	 }
	static void sort(int[] arr ) {
		 ArrayList<Integer> al = new ArrayList<>();
		 for(int e:arr) al.add(e);
		 Collections.sort(al);
		 for(int i = 0 ; i<al.size(); i++) arr[i] = al.get(i);
	 }
	static void sort(char[] arr) {
		ArrayList<Character> al = new ArrayList<Character>();
		for(char cc:arr) al.add(cc);
		Collections.sort(al);
		for(int i = 0 ;i<arr.length ;i++) arr[i] = al.get(i);
	}
	static void rvrs(int[] arr) {
		int i =0 , j = arr.length-1;
		while(i>=j) {
			int temp = arr[i];
			arr[i] = arr[j];
			arr[j] = temp;
			i++;
			j--;
		}
	}
	static void rvrs(long[] arr) {
		int i =0 , j = arr.length-1;
		while(i>=j) {
			long temp = arr[i];
			arr[i] = arr[j];
			arr[j] = temp;
			i++;
			j--;
		}
	}

	static long mod_mul(long a , long b ,long mod) {
		return ((a%mod)*(b%mod))%mod;
	}
	 static long gcd(long a, long b)
	  {      
	     if (b == 0)
	        return a;
	     return gcd(b, a % b); 
	  }
	 static boolean[] prime(int num) {
			boolean[] bool = new boolean[num];
		     
		      for (int i = 0; i< bool.length; i++) {
		         bool[i] = true;
		      }
		      for (int i = 2; i< Math.sqrt(num); i++) {
		         if(bool[i] == true) {
		            for(int j = (i*i); j<num; j = j+i) {
		               bool[j] = false;
		            }
		         }
		      }
		      if(num >= 0) {
		    	  bool[0] = false;
		    	  bool[1] = false;
		      }
		      
		      return bool;
		}

	 static long modInverse(long a, long m)
	    {
	        long g = gcd(a, m);
	       
	          return   power(a, m - 2, m);
	        
	    }
	   
	 static long power(long x, long y, long m){
	        if (y == 0) return 1; long p = power(x, y / 2, m) % m; p = (int)((p * (long)p) % m);
	        if (y % 2 == 0) return p; else return (int)((x * (long)p) % m); }
	   
     static class Combinations{
	    	 long[] fac;
	    	 long[] inf;
	    	  public Combinations(long N , long mod) {
				fac = new long[(int)N+1];
				inf = new long[(int)N+1];
				fac[0] = 1;
				for(int i =1 ; i<=N ; i++) fac[i] = (fac[i-1]*i)%mod;
			    long[] naturalNumInverse = new long[(int)N+1];
				naturalNumInverse[0] = naturalNumInverse[1] = 1;
			    for (int i = 2; i <= N; i++)
			        naturalNumInverse[i] = naturalNumInverse[(int)(mod % i)] * (mod - mod / i) % mod;
			    
			    inf[0] = inf[1] = 1;
			    
			    for (int i = 2; i <= N; i++)
			        inf[i] = (naturalNumInverse[i] * inf[i - 1]) % mod;
			}
	    	  
	    	  long ncr(long N, long R, long mod)
	    	  {		if(R<0 || R>N ) return 0;
	    		    long ans = ((fac[(int)N] * inf[(int)R])
	    		              % mod * inf[(int)(N - R)])
	    		             % mod;
	    		    return ans;
	    		}
	      }
	      static class DisjointUnionSets {
			    int[] rank, parent;
			    int n;
			  
			    public DisjointUnionSets(int n)
			    {
			        rank = new int[n];
			        parent = new int[n];
			        this.n = n;
			        makeSet();
			    }
			  
			    void makeSet()
			    {
			        for (int i = 0; i < n; i++) {
			          
			            parent[i] = i;
			        }
			    }
			  
			    int find(int x)
			    {
			        if (parent[x] != x) {
			        
			            parent[x] = find(parent[x]);
			  
			        }
			  
			        return parent[x];
			    }
			  
			    void union(int x, int y)
			    {
			        int xRoot = find(x), yRoot = find(y);
			  
			        if (xRoot == yRoot)
			            return;
			  
			        if (rank[xRoot] < rank[yRoot])
			  
			            parent[xRoot] = yRoot;
			  
			        else if (rank[yRoot] < rank[xRoot])
			  
			            parent[yRoot] = xRoot;
			  
			        else
			        {
			            parent[yRoot] = xRoot;
			  
			            rank[xRoot] = rank[xRoot] + 1;
			        }
			    }
			}
	      
/************************************************ Query **************************************************************************************/	  
	      static class SparseTable{
	    		
	    		private long[][] st;
	    		
	    		SparseTable(long[] arr){
	    			int n = arr.length;
	    			st = new long[n][25];
	    			log = new int[n+2];
	    			build_log(n+1);
	    			build(arr);
	    		}
	    		
	    		private void build(long[] arr) {
	    			int n = arr.length;
	    			
	    			for(int i = n-1 ; i>=0 ; i--) {
	    				for(int j = 0 ; j<25 ; j++) {
	    					int r = i + (1<<j)-1;
	    					if(r>=n) break;
	    					if(j == 0 ) st[i][j] = arr[i];
	    					else st[i][j] = Math.min(st[i][j-1] , st[ i + ( 1 << (j-1) ) ][ j-1 ] );
	    				}
	    			}
	    		}
	    		public long gcd(long a  ,long b) {
	    			if(a == 0) return b;
	    			return gcd(b%a , a);
	    		}
	    		public long query(int l ,int r) {
	    			int w = r-l+1;
	    			int power = log[w];
	    			return Math.min(st[l][power],st[r - (1<<power) + 1][power]);
	    		}
	    		private int[] log;
	    		void build_log(int n) {
	    			log[1] = 0;
	    			for(int i = 2 ; i<=n ; i++) {
	    				log[i] = 1 + log[i/2];
	    			}
	    		}
	    	}
//	  	static int query(int[] tree , int ss ,int se ,int qs , int qe,int index) {
//			
//			if(ss>=qs && se<=qe) return tree[index];
//			
//			if(qe<ss || se<qs) return Integer.MAX_VALUE;
//			
//			int mid = (ss + se)/2;
//			int left = query(tree , ss , mid , qs ,qe , 2*index);
//			int right= query(tree ,mid + 1 , se , qs ,qe , 2*index+1);
//			return Math.min(left, right);
//		}
//		static void buildTree(int[] a ,int s ,int e ,int[] tree ,int index ) {
//			if(s == e) {
//				tree[index] = a[s];
//				return;
//			}
//		
//			int mid = (s+e)/2;
//			
//			buildTree(a, s,  mid, tree, 2*index);
//			buildTree(a, mid+1, e, tree, 2*index+1);
//			
//			tree[index] = tree[2*index] + tree[2*index+1];
//		}
	  
/* ***************************************************************************************************************************************************/	 
	 
	      static FR sc = new FR();
	 static StringBuilder sb = new StringBuilder();
	 public static void main(String args[]) throws IOException {
	
		 int tc = 1;
		  tc = sc.nextInt();
		 
		 while(tc-->0) {
			 TEST_CASE();
			 
		 }
		 System.out.println(sb);
	 }
	 static void TEST_CASE() {
		 char[] str = sc.next().toCharArray();
		 int ans = 2;
		 if(zero(str)) {
			 sb.append("1\n");
			 return;
		 }
		 if(one(str)) {
			 sb.append("0\n");
			 return;
		 }
		 int c = 0;
		 int i = 0;
		 int n = str.length;
		 while(i<n) {
			 char cc = str[i];
			 while(i<n && cc == str[i]) {
				 i++;
			 }
			 if(cc == '0') c++;
		 }
		 sb.append(Math.min(c, ans)+"\n");
	 }
	 static boolean one(char[] arr) {
		 for(char cc:arr) {
			 if(cc != '1') return false;
		 }
		 return true;
	 }
	 static boolean zero(char[] arr) {
		 for(char cc:arr) {
			 if(cc != '0') return false;
		 }
		 return true;
	 }
}



/*******************************************************************************************************************************************************/

/***

*/


