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

public class cfka1399a
{

  static BufferedReader br;
  static PrintWriter out;
  static StringTokenizer st;
  static int mod=1000000007;
  static long fact[] =new long[1000007];
  static int sieve[] = new int[100005];
  static int N = 100000;
  static long []spf = new long[1000005];
  static long []hash = new long[1000001];

  public static void main(String[] args) throws IOException 
  {
    br = new BufferedReader(new InputStreamReader(System.in));
    out = new PrintWriter(new OutputStreamWriter(System.out));
    //br = new BufferedReader(new FileReader("in.txt"));
    //out = new PrintWriter(new BufferedWriter(new FileWriter("output.txt")));
    
    try{
      //Your Solve
      //1 means prime 0 means not prime
       int t = readInt();
       while(t-->0){
        String s = next();
        int sum=0;
        for(int i=0;i<s.length();i++){
          if(s.charAt(i)=='0')
          sum=sum+1;
        }
        boolean f1 = s.contains("1");
        boolean f2= s.contains("0");
        if(sum>=2&&(f1))
          System.out.println(2);
        else if(sum>=2&&(!f1))
          System.out.println(1);
        else if(sum<2&&f1&&f2)
          System.out.println(1);
        else System.out.println(sum);
       }
      //upto here  
    }catch(Exception e){
      return;
    }
      
  
  }
  static void solve() throws IOException{
    spf2();
    int q = readInt();
    while(q-->0){
      int x = readInt();
      System.out.println(hash[x]);
    }
  }
  static long N1 = 1000005;
  static void spf2(){
    for(long p=1;p<=N1;p++){
      spf[(int)p]=p;
    }
    
    for(long i=2;i*i<=N1;i++){
      if(spf[(int)i]==i){
        hash[(int)i]=1;
      for(long j=(i*i);j<=N1;j+=i){
          if(spf[(int)j]==j){
            spf[(int)j]=i;
            hash[(int)i]+=1;
          }
        }
      }
    }
  }
  static String next() throws IOException 
  {
    while (st == null || !st.hasMoreTokens())
      st = new StringTokenizer(br.readLine().trim());
    return st.nextToken();
  }
    //extended
    static int gcd(int a, int b, int x, int y)
    {
        // Base Case
        if (a == 0)
        {
            x = 0;
            y = 1;
            return b;
        }
 
        int x1=1, y1=1; // To store results of recursive call
        int gcd = gcd(b%a, a, x1, y1);
 
        // Update x and y using results of recursive
        // call
        x = y1 - (b/a) * x1;
        y = x1;
 
        return gcd;
    }
    
  static long readLong() throws IOException 
  {
    return Long.parseLong(next());
  }

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

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

  static char readCharacter() throws IOException 
  {
    return next().charAt(0);
  }

  static String readLine() throws IOException 
  {
    return br.readLine().trim();
  }
  static int binarysearch(int []arr,int n) throws IOException{
    int low = 0;
    int high = arr.length-1;
    while(low<=high){
      int mid = (low+high)/2;
      if(arr[mid]==n)
        return mid;
      else if(arr[mid]<n){
        low = mid+1;
      }
      else if(arr[mid]>n){
        high = mid-1;
      }
      
    }
    return -1;
  }
  static long nCr(long n,long r){
    long i=0;
    long res = 1;
    for(i=0;i<r;i++)
    
            {
              res=(res*(n-i))/(i+1); 
              
            }
        return res;
  }
  static long fact(long n){
    long sum=1;
    for(long i=1;i<=n;i++){
      sum*=i;
    }
    return sum;
  }
  static void precompute(){
         fact[0] =1;
        for(int i=1;i<=1000000;i++){
            fact[i]=(fact[i-1]*i)%mod;
        }
    }
    static long modPow(long base, long n){
    long ans=1;
    while(n>0){
        if(n%2==0){
        base = (base*base)%mod;
        n=n/2;
        }else{
          ans = (ans*base)%mod;
          n=n-1;
      }
    }
    return ans;
}
  static int firstoccurence(int[] nums,int target){
    int start = 0;
    int end = nums.length -1;
    int res = -1;
    while(start<=end){
      int mid = start+(end-start)/2;
      if(target==nums[mid]){
        res=mid;
        end = mid-1;
      }
      else if(target<nums[mid])
        end = mid-1;
      else
        start = mid+1;
    }
    return res;
  }
  static int lastoccurence(int[] nums,int target){
    int start=0;
    int end = nums.length-1;
    int res= -1;
    while(start<=end){
      int mid = start + (end-start)/2;
      if(target==nums[mid]){
        res = mid;
        start = mid+1;
      }
      else if(target<nums[mid])
        end = mid-1;
      else
        start = mid+1;
    }
    return res;
  }
  static boolean prime(int n){
    int count=1;
    for(int i=2;i*i<=n;i++){
      if(n%i==0)
        return false;
    }
    return true;
  }
  static void generatesieve(){
    for(int i=2;i<=N;i++) 
      sieve[i] = 1;
    for(int j=2;j*j<=N;j++){
      if(sieve[j]==0)
        continue;
      for(int k=2*j;k<=N;k=k+j){
        sieve[k] = 0;
        }
    }
  }
  static void printprimes(int l,int r){
    generatesieve();
    for(int i=l;i<=r;i++){
      if(sieve[i]==1){
      System.out.println(i);
      }
    }
  }
  
  static void createSPF() {
    for (int i = 2; i <= spf.length; i++) spf[i] = i;
   
    for (int j = 2; j * j <= spf.length; j++) {
      if (spf[j] != j) continue;
   
      for (int k = j * j; k <= spf.length; k = k + j) {
        if(spf[k]==k) spf[k] = j; 
      }
    }
  }
  static void printinFactors(long n) {
  while(n!=1) {
    System.out.println(spf[(int)n]+" ");
    n = n / spf[(int)n]; 
    }
  }
  
}


