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;
unsigned seed = chrono::system_clock::now().time_since_epoch().count();
mt19937 Rand(seed);
uniform_int_distribution<long long> range(0, 1ll << 32);
inline void ucin() {
  ios::sync_with_stdio(0);
  cin.tie(0);
}
template <class T>
inline void chkmax(T &x, const T &y) {
  if (x < y) x = y;
}
template <class T>
inline void chkmin(T &x, const T &y) {
  if (x > y) x = y;
}
const int N = 110;
const int mod = 1e9 + 7;
int qpow(int a, int b) {
  int ans = 1;
  for (; b >= 1; b >>= 1, a = (long long)a * a % mod)
    if (b & 1) ans = (long long)ans * a % mod;
  return ans;
}
struct String {
  string pre, suf;
  bitset<1024 + 10> tag[10];
  void init(char *s) {
    int n = strlen(s + 1);
    for (int i = 1; i <= n; ++i) {
      int z = 0;
      for (int k = 1; k <= 9; ++k) {
        if (i + k - 1 > n) break;
        z = (z << 1) + (s[i + k - 1] & 15);
        tag[k][z] = 1;
      }
    }
    for (int i = 1; i <= min(n, 9); ++i) pre.push_back(s[i]);
    for (int i = max(1, n - 8); i <= n; ++i) suf.push_back(s[i]);
  }
  void merge(String A, String B) {
    for (int k = 1; k <= 9; ++k) tag[k] = A.tag[k] | B.tag[k];
    pre = A.pre + B.pre;
    pre.resize(min((int)pre.size(), 9));
    suf = A.suf + B.suf;
    while (suf.size() > 9) suf.erase(suf.begin());
    int L = A.suf.size(), R = B.pre.size();
    for (int i = 1; i <= 8; ++i)
      if (i <= L)
        for (int j = 1; j <= 8; ++j)
          if (j <= R) {
            if (i + j > 9) break;
            int z = 0;
            for (int k = L - i; k <= L - 1; ++k) z = (z << 1) + (A.suf[k] & 15);
            for (int k = 0; k <= j - 1; ++k) z = (z << 1) + (B.pre[k] & 15);
            tag[i + j][z] = 1;
          }
  }
  int result() {
    for (int k = 1; k <= 9; ++k) {
      if (tag[k].count() != (1 << k)) {
        return k - 1;
      }
    }
    return 9;
  }
} s[N * 2];
int n, m;
int main() {
  scanf("%d", &n);
  static char str[N];
  for (int i = 1; i <= n; ++i) {
    scanf("%s", str + 1);
    s[i].init(str);
  }
  scanf("%d", &m);
  for (int i = 1; i <= m; ++i) {
    int x, y;
    scanf("%d%d", &x, &y);
    s[n + i].merge(s[x], s[y]);
    printf("%d\n", s[n + i].result());
  }
  return 0;
}