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.
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
using namespace std;
#define FIO                       \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
#define pi acos(-1.0)
#define ll long long
#define ull unsigned ll
#define EPS 1e-12
#define MV 1e18
#define MX 10000008
#define mx 2000056
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define MEM(a, x) memset(a, x, sizeof(a))
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) (a * (b / gcd(a, b)))
#define vii vector<int>
#define vll vector<ll>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pip pair<int, pii>
#define pul pair<ull, ull>
#define mii map<int, int>
#define mll map<ll, ll>
#define qii queue<int>
#define dii deque<int>
#define vip vector<pair<int, int>>
#define vlp vector<pair<ll, ll>>
#define djk priority_queue<pll, vlp, greater<pll>>
#define pb push_back
#define mp make_pair
#define SP(x, y) fixed << setprecision((x)) << (y)
const int INF = INT_MAX;
int fx[] = {+1, -1, +0, +0};
int fy[] = {+0, +0, +1, -1};

// freopen("data.txt", "r", stdin);
// freopen("dataOut.txt", "w", stdout);
///cout<<"Case "<<z++<<": "<<__<<endl;

typedef bool (*comp)(pii, pii);
void solve()
{
    string s;
    cin >> s;
    int z = count(all(s), '0');
    int o = count(all(s), '1');
    if (z == s.size())
    {
        cout << 1 << endl;
        return;
    }
    if (o == s.size())
    {
        cout << 0 << endl;
        return;
    }
    int cnt = 0;
    for (int i = 0;i<s.size(); i++)
    {
        if(s[i]=='0')
            cnt++;
        else
        {
            if(cnt==z)
            {
                cout << 1 << endl;
                return;
            }
            cnt = 0;
        }
    }
    if(!cnt)
        cout << 1 << endl;
    else
        cout << 2 << endl;
}
int main()
{
    int x;
    cin >> x;
    while (x--)
    {
        solve();
    }
}