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>
int f(int a, int b, int c) {
  if (a && b)
    return 2;
  else if (a && c)
    return 1;
  else if (b && c)
    return 0;
}
int f1(int a, int b) {
  if (a && !b) {
    if (a - '0')
      return 0;
    else
      return 1;
  }
  if (a && b) {
    if (!(a - '0') || !(b - '0'))
      return 1;
    else
      return 0;
  }
}
int main() {
  int t, i = 1;
  scanf("%d", &t);
  getchar();
  while (t--) {
    char ch;
    int s1 = 0, s2 = 0;
    int flag = 0, flagg = 0, flag0 = 0, flag1 = 0, flag2 = 0;
    int end = 0;
    while ((ch = getchar()) != '\n') {
      if (ch == '0') flag0 = 1;
      if (ch == '1') flag1 = 1;
      if (ch == '2') flag2 = 1;
      if (!flag) {
        flag = ch;
        continue;
        s1++;
      }
      if (ch != flag && !flagg)
        flagg = ch;
      else
        s1++;
      if (ch != flagg) {
        end = 1;
        s2++;
      }
    }
    if (s1 == s2) end = 0;
    if (end == 1)
      printf("%d\n", f(flag0, flag1, flag2));
    else
      printf("%d\n", f1(flag, flagg));
  }
  return 0;
}
