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>
using namespace std;
using namespace std::chrono;
const long long big = 1000000007ll;
const long long big2 = 1000000009ll;
long long n, m, k, q, w, h, T;
const long long maxl = 12;
bool exist[201][maxl][(1 << maxl)] = {0};
vector<string> fir;
vector<string> las;
long long now = 0;
long long conc(long long i, long long j) {
  string fs = "";
  for (long long c1 = 0; c1 < maxl; c1++) {
    if (c1 >= fir[i].length()) {
      long long j2 = c1 - fir[i].length();
      if (j2 < fir[j].length()) {
        fs += fir[j][j2];
      }
    } else {
      fs += fir[i][c1];
    }
  }
  string ls = "";
  long long li = las[i].length();
  long long lj = las[j].length();
  for (long long c1 = 0; c1 < maxl; c1++) {
    if (c1 >= las[j].length()) {
      long long j2 = c1 - lj;
      if (j2 < li) {
        ls += las[i][li - j2 - 1];
      }
    } else {
      ls += las[j][lj - c1 - 1];
    }
  }
  reverse(ls.begin(), ls.end());
  fir.push_back(fs);
  las.push_back(ls);
  for (long long c1 = 0; c1 < maxl; c1++) {
    for (long long c2 = 0; c2 < (1 << (c1 + 1)); c2++) {
      exist[now][c1][c2] |= exist[i][c1][c2];
      exist[now][c1][c2] |= exist[j][c1][c2];
    }
  }
  string mid = las[i] + fir[j];
  for (long long c2 = 0; c2 < maxl; c2++) {
    for (long long c3 = 0; c3 < mid.length() - c2; c3++) {
      long long t = 0;
      for (long long c4 = 0; c4 < c2 + 1; c4++) {
        t *= 2;
        t += mid[c3 + c4] - '0';
      }
      exist[now][c2][t] = 1;
    }
  }
  for (long long c1 = 0; c1 < maxl; c1++) {
    for (long long c2 = 0; c2 < (1 << (c1 + 1)); c2++) {
      if (exist[now][c1][c2] == 0) return c1;
    }
  }
  return maxl;
}
int main() {
  long long a, b, c, d;
  cin >> n;
  for (long long c1 = 0; c1 < n; c1++) {
    string s;
    cin >> s;
    string fs = "";
    for (long long c2 = 0; c2 < maxl; c2++) {
      if (c2 >= s.length()) break;
      fs += s[c2];
    }
    string ls = "";
    for (long long c2 = s.length() - maxl; c2 < s.length(); c2++) {
      if (c2 < 0) continue;
      ls += s[c2];
    }
    fir.push_back(fs);
    las.push_back(ls);
    for (long long c2 = 0; c2 < maxl; c2++) {
      for (long long c3 = 0; c3 < s.length() - c2; c3++) {
        long long t = 0;
        for (long long c4 = 0; c4 < c2 + 1; c4++) {
          t *= 2;
          t += s[c3 + c4] - '0';
        }
        exist[c1][c2][t] = 1;
      }
    }
  }
  now = n - 1;
  cin >> m;
  for (long long c1 = 0; c1 < m; c1++) {
    cin >> a >> b;
    a--;
    b--;
    now++;
    cout << conc(a, b) << "\n";
  }
  return 0;
}