You are given two binary strings x and y, which are binary representations of some two integers (let's denote these integers as f(x) and f(y)). You can choose any integer k ≥ 0, calculate the expression s_k = f(x) + f(y) ⋅ 2^k and write the binary representation of s_k in reverse order (let's denote it as rev_k). For example, let x = 1010 and y = 11; you've chosen k = 1 and, since 2^1 = 10_2, so s_k = 1010_2 + 11_2 ⋅ 10_2 = 10000_2 and rev_k = 00001.

For given x and y, you need to choose such k that rev_k is lexicographically minimal (read notes if you don't know what does "lexicographically" means).

It's guaranteed that, with given constraints, k exists and is finite.

Input

The first line contains a single integer T (1 ≤ T ≤ 100) — the number of queries.

Next 2T lines contain a description of queries: two lines per query. The first line contains one binary string x, consisting of no more than 10^5 characters. Each character is either 0 or 1.

The second line contains one binary string y, consisting of no more than 10^5 characters. Each character is either 0 or 1.

It's guaranteed, that 1 ≤ f(y) ≤ f(x) (where f(x) is the integer represented by x, and f(y) is the integer represented by y), both representations don't have any leading zeroes, the total length of x over all queries doesn't exceed 10^5, and the total length of y over all queries doesn't exceed 10^5.

Output

Print T integers (one per query). For each query print such k that rev_k is lexicographically minimal.

Example

Input


4
1010
11
10001
110
1
1
1010101010101
11110000


Output


1
3
0
0

Note

The first query was described in the legend.

In the second query, it's optimal to choose k = 3. The 2^3 = 1000_2 so s_3 = 10001_2 + 110_2 ⋅ 1000_2 = 10001 + 110000 = 1000001 and rev_3 = 1000001. For example, if k = 0, then s_0 = 10111 and rev_0 = 11101, but rev_3 = 1000001 is lexicographically smaller than rev_0 = 11101.

In the third query s_0 = 10 and rev_0 = 01. For example, s_2 = 101 and rev_2 = 101. And 01 is lexicographically smaller than 101.

The quote from Wikipedia: "To determine which of two strings of characters comes when arranging in lexicographical order, their first letters are compared. If they differ, then the string whose first letter comes earlier in the alphabet comes before the other string. If the first letters are the same, then the second letters are compared, and so on. If a position is reached where one string has no more letters to compare while the other does, then the first (shorter) string is deemed to come first in alphabetical order."
#include <bits/stdc++.h>
using namespace std;
long long power(long long a, long long n, long long d) {
  long long res = 1;
  while (n) {
    if (n & 1 != 0) {
      res = ((res % d) * ((a % d + d) % d)) % d;
      n--;
    } else {
      a = ((((a % d + d) % d)) * (((a % d + d) % d))) % d;
      n >>= 1;
    }
  }
  return res;
}
void SieveOfEratosthenes(long long N, vector<long long>& s) {
  s[0] = 0;
  s[1] = 0;
  s[2] = 1;
  s[3] = 1;
  bool prime[N + 1];
  memset(prime, true, sizeof(prime));
  for (long long p = 2; p * p <= N; p++) {
    if (prime[p] == true) {
      for (long long i = p * p; i <= N; i += p) {
        prime[i] = false;
        s[i] = 0;
      }
    }
  }
}
struct not_digit {
  bool operator()(const char c) { return c != ' ' && !std::isdigit(c); }
};
void extractNum(string str, vector<long long>& numbers) {
  not_digit not_a_digit;
  string::iterator end = std::remove_if(str.begin(), str.end(), not_a_digit);
  string all_numbers(str.begin(), end);
  stringstream ss(all_numbers);
  for (long long i = 0; ss >> i;) {
    numbers.push_back(i);
  }
}
void getWords(string str, vector<string>& vec, unordered_set<string>& Set) {
  string word;
  stringstream iss(str);
  while (iss >> word) {
    Set.insert(word);
    vec.push_back(word);
  }
}
bool isPower(long long n) {
  if (n <= 1) return true;
  for (long long x = 2; x <= sqrt(n); x++) {
    unsigned p = x;
    while (p <= n) {
      p *= x;
      if (p == n) return true;
    }
  }
  return false;
}
string decimalToBinary(long long n) {
  string s = bitset<64>(n).to_string();
  const auto loc1 = s.find('1');
  if (loc1 != string::npos) return s.substr(loc1);
  return "0";
}
double slope(long long x1, long long y1, long long x2, long long y2) {
  double angle;
  angle = (y2 - y1) / (double)(x2 - x1);
  return angle;
}
bool isPrime(long long n) {
  if (n == 1)
    return false;
  else {
    for (long long i = 2; i * i <= n; i++) {
      if (n % i == 0) return false;
    }
    return true;
  }
}
long long Power(long long a, long long n) {
  long long res = 1;
  if (n == 0) return 1;
  while (n) {
    if (n & 1 != 0) {
      res *= a;
      n--;
    } else {
      a *= a;
      n >>= 1;
    }
  }
  return res;
}
long long Mod(long long x) {
  return ((x % 1000000007 + 1000000007) % 1000000007);
}
long long add(long long a, long long b) { return Mod(Mod(a) + Mod(b)); }
long long mul(long long a, long long b) { return Mod(Mod(a) * Mod(b)); }
const long long N = 2e5 + 2;
long long fact[N];
void precalc() {
  fact[0] = 1;
  for (long long i = 1; i < N; i++) {
    fact[i] = mul(fact[i - 1], i);
  }
}
long long inv(long long x) { return pow(x, 1000000007 - 2); }
long long divide(long long a, long long b) { return mul(a, inv(b)); }
long long nCr(long long n, long long r) {
  return divide(fact[n], mul(fact[r], fact[n - r]));
}
long long solve() {
  long long a, b;
  cin >> a >> b;
  long long diff = b - a;
  long long res = 0, one = 1;
  string s;
  for (long long i = 0; i < log2(b) + 1; i++) {
    if (diff > (one << i))
      continue;
    else if (a & (one << i) && b & (one << i))
      res += (one << i);
  }
  return res;
}
long long cost(long long L, long long R, char ch, string& s) {
  long long cnt = 0;
  for (long long i = L; i <= R; i++)
    if (s[i] != ch) cnt++;
  return cnt;
}
long long getMin(long long l, long long r, char ch, string& s) {
  if (l == r) {
    if (s[l] == ch)
      return 0;
    else
      return 1;
  }
  long long mid = (l + r) >> 1;
  return min(cost(l, mid, ch, s) + getMin(mid + 1, r, ch + 1, s),
             cost(mid + 1, r, ch, s) + getMin(l, mid, ch + 1, s));
}
long long getMax(long long base, long long ele) {
  long long i, num = 1, temp = 0;
  while (num < ele) {
    num *= base;
    temp++;
  }
  return temp;
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  long long x;
  cin >> x;
  while (x--) {
    long long n, i, value, k, flag = 1, sumxor = 0, sum = 0;
    string s, p;
    cin >> s >> p;
    long long sSize = s.size(), pSize = p.size(), index = 0;
    for (i = pSize - 1; i >= 0; i--) {
      if (p[i] == '1') {
        index = i;
        break;
      }
    }
    long long f = sSize - 1 - (pSize - 1 - i), ans = 0;
    for (i = f; i >= 0; i--) {
      if (s[i] == '1') break;
      ans++;
    }
    cout << ans << "\n";
  }
}
