Problem: You are given n strings s1, s2, ..., sn consisting of characters 0 and 1. m operations are performed, on each of them you concatenate two existing strings into a new one. On the i-th operation the concatenation saisbi is saved into a new string sn + i (the operations are numbered starting from 1). After each operation you need to find the maximum positive integer k such that all possible strings consisting of 0 and 1 of length k (there are 2k such strings) are substrings of the new string. If there is no such k, print 0.

Input

The first line contains single integer n (1 ≤ n ≤ 100) — the number of strings. The next n lines contain strings s1, s2, ..., sn (1 ≤ |si| ≤ 100), one per line. The total length of strings is not greater than 100.

The next line contains single integer m (1 ≤ m ≤ 100) — the number of operations. m lines follow, each of them contains two integers ai abd bi (1 ≤ ai, bi ≤ n + i - 1) — the number of strings that are concatenated to form sn + i.

Output

Print m lines, each should contain one integer — the answer to the question after the corresponding operation.

Example

Input

5
01
10
101
11111
0
3
1 2
6 5
4 4


Output

1
2
0

Note

On the first operation, a new string "0110" is created. For k = 1 the two possible binary strings of length k are "0" and "1", they are substrings of the new string. For k = 2 and greater there exist strings of length k that do not appear in this string (for k = 2 such string is "00"). So the answer is 1.

On the second operation the string "01100" is created. Now all strings of length k = 2 are present.

On the third operation the string "1111111111" is created. There is no zero, so the answer is 0.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
#pragma optimise GCC(-O2)
using namespace std;
mt19937_64 rang(
    chrono::high_resolution_clock::now().time_since_epoch().count());
long long rng(long long lim) {
  uniform_int_distribution<long long> uid(0, lim - 1);
  return uid(rang);
}
long long INF = LLONG_MAX;
const long long M = 1000000007, M2 = 998244353, M3 = 2013265921;
long long powm(long long, long long, long long);
long long modI(long long, long long);
long long PrimRoot(long long p, long long x);
void fft(vector<long long>& a, long long n, bool invert, long long m,
         long long x);
void PolyMult(vector<long long>& a, vector<long long>& b, vector<long long>& v,
              long long m, long long x);
struct obj {
  string pre, suff;
  long long count[11][(1 << 10)] = {0};
  long long lth;
};
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  long long n;
  cin >> n;
  vector<obj> v;
  obj x;
  v.push_back(x);
  for (long long i = 0; i < n; i++) {
    string s;
    cin >> s;
    long long n = s.length();
    long long len = min((long long)9, n);
    string p = s.substr(0, len);
    reverse(s.begin(), s.end());
    string ff = s.substr(0, len);
    reverse(s.begin(), s.end());
    obj x;
    x.pre = p, x.suff = ff;
    x.lth = s.length();
    for (long long parameter = 1; parameter < 10; parameter++)
      for (long long j = s.length() - 1; j >= parameter - 1; j--) {
        long long mask = 0;
        for (long long i = 0; i < parameter; i++) {
          if (j - i < 0) assert(false);
          if (s[j - i] - '0') mask += (1 << i);
        }
        x.count[parameter][mask] = 1;
      }
    v.push_back(x);
  }
  long long m;
  cin >> m;
  for (long long qrrryyyysdgdgs = 0; qrrryyyysdgdgs < m; qrrryyyysdgdgs++) {
    long long a;
    cin >> a;
    long long b;
    cin >> b;
    obj x;
    for (long long param = 1; param < 10; param++)
      for (long long i = 0; i < 1024; i++) {
        if (v[a].count[param][i] || v[b].count[param][i]) x.count[param][i] = 1;
      }
    string p1 = v[a].suff, p2 = v[b].pre;
    for (long long param = 1; param < 10; param++)
      for (long long i = 1; i < p1.length() + 1; i++) {
        string temp = p1.substr(0, i);
        reverse(temp.begin(), temp.end());
        long long len2 = min(param - i, (long long)p2.length());
        if (len2 <= 0 || i + len2 != param) continue;
        temp += (p2.substr(0, len2));
        reverse(temp.begin(), temp.end());
        assert(temp.length() == param);
        long long mask = 0;
        for (long long j = 0;
             j < min((long long)param, (long long)temp.length()); j++)
          if (temp[j] - '0') mask += (1 << j);
        x.count[param][mask] = 1;
      }
    x.lth = v[a].lth + v[b].lth;
    string temp = v[a].pre + v[b].pre;
    x.pre = temp.substr(0, min((long long)10, (long long)temp.size()));
    temp = v[b].suff + v[a].suff;
    x.suff = temp.substr(0, min((long long)10, (long long)temp.size()));
    v.push_back(x);
    long long ans = 0;
    for (long long k = 1; k < 10; k++) {
      bool flag = 1;
      for (long long i = 0; i < (1 << k); i++)
        if (!x.count[k][i]) flag = 0;
      if (flag)
        ans = k;
      else
        break;
    }
    cout << ans << endl;
  }
}
long long powm(long long a, long long b, long long c = M) {
  long long res = 1;
  while (b) {
    if (b & 1) res = (res * a) % c;
    a = (a * a) % c;
    b >>= 1;
  }
  return res;
}
long long modI(long long a, long long m = M) {
  long long m0 = m, y = 0, x = 1;
  if (m == 1) return 0;
  while (a > 1) {
    long long q = a / m;
    long long t = m;
    m = a % m;
    a = t;
    t = y;
    y = x - q * y;
    x = t;
  }
  if (x < 0) x += m0;
  return x;
}
long long PrimRoot(long long p, long long x) {
  vector<long long> v;
  long long t = p - 1;
  for (long long i = 2; i * i <= t; i++)
    if (t % i == 0) {
      v.push_back((p - 1) / i);
      while (t % i == 0) t /= i;
    }
  if (t > 1) v.push_back((p - 1) / t);
  for (long long i = x + 1; i < p; i++) {
    long long flag = 0;
    for (auto x : v)
      if (powm(i, x, p) == 1) {
        flag = 1;
        break;
      }
    if (flag == 0) return i;
  }
  return 0;
}
void fft(vector<long long>& a, long long n, bool invert, long long m,
         long long x) {
  long long lg_n = __builtin_ctzll(n);
  for (long long i = 0, y = 0; i < n; i++) {
    for (long long j = 0; j < lg_n; j++)
      if ((1LL << j) & i) y |= (1LL << (lg_n - j - 1));
    if (y > i) swap(a[i], a[y]);
  }
  if (invert) x = modI(x, m);
  for (long long s = 2; s <= n; s <<= 1) {
    long long y = powm(x, (n / s), m);
    for (long long j = 0; j < (n / s); j++) {
      long long r = 1;
      for (long long i = 0; i < s / 2; i++) {
        long long u = a[i + j * s], v = (r * a[i + j * s + (s / 2)]) % m;
        a[i + j * s] = (u + v) % m;
        a[i + j * s + (s / 2)] = (u - v + m) % m;
        r = r * y % m;
      }
    }
  }
  if (invert) {
    long long invn = modI(n, m);
    for (long long i = 0; i < n; i++) a[i] = (a[i] * invn) % m;
  }
  return;
}
void PolyMult(vector<long long>& a, vector<long long>& b, vector<long long>& v,
              long long m, long long x) {
  long long n = 1;
  while (n < ((long long)a.size()) + ((long long)b.size())) n <<= 1;
  vector<long long> fa(a.begin(), a.end());
  fa.resize(n, 0);
  vector<long long> fb(b.begin(), b.end());
  fb.resize(n, 0);
  long long y = powm(x, (m - 1) / n, m);
  fft(fa, n, false, m, y);
  fft(fb, n, false, m, y);
  v.resize(n, 0);
  for (long long i = 0; i < n; i++) v[i] = ((fa[i] * fb[i]) % m);
  fft(v, n, true, m, y);
  return;
}