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;
const int N = 100 + 5;
const int K = 30;
int n, m;
string s[N * 2], st[N * 2], nd[N * 2];
int sz[N * 2];
int res[N * 2];
bitset<66000> a[N * 2][15];
void compute(int i) {
  for (int k = 1; k < 15; k++) {
    for (int j = 0; j + k - 1 < s[i].size(); j++) {
      int cur = 0;
      for (int t = j; t < j + k; t++) cur = (cur << 1) | (s[i][t] - '0');
      a[i][k].set(cur);
    }
    if (a[i][k].count() == (1 << k)) res[i] = k;
  }
}
void addBeg(int i, int x) {
  for (int k = res[i] + 1; k < 15; k++) {
    int cur = x - '0';
    for (int j = 0; j < k - 1; j++) cur = (cur << 1) | (st[i][j] - '0');
    a[i][k].set(cur);
    if (a[i][k].count() == (1 << k)) res[i] = k;
  }
  st[i] = (char)x + st[i];
  st[i] = st[i].substr(0, K);
}
void addEnd(int i, int x) {
  for (int k = res[i] + 1; k < 15; k++) {
    int cur = 0;
    for (int j = nd[i].size() - (k - 1); j < nd[i].size(); j++)
      cur = (cur << 1) | (nd[i][j] - '0');
    cur = (cur << 1) | (x - '0');
    a[i][k].set(cur);
    if (a[i][k].count() == (1 << k)) res[i] = k;
  }
  nd[i] += (char)x;
  nd[i] = nd[i].substr(nd[i].size() - K, K);
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    cin >> s[i];
    sz[i] = s[i].size();
    st[i] = nd[i] = s[i];
    compute(i);
  }
  scanf("%d", &m);
  for (int i = 1; i <= m; i++) {
    int x, y;
    scanf("%d %d", &x, &y);
    if (sz[x] + sz[y] <= 2 * K) {
      s[n + i] = s[x] + s[y];
      st[n + i] = nd[n + i] = s[n + i];
      sz[n + i] = s[n + i].size();
      compute(n + i);
    } else {
      sz[n + i] = 500;
      if (sz[x] <= K) {
        st[n + i] = st[y];
        nd[n + i] = nd[y];
        for (int k = 0; k < 15; k++) a[n + i][k] = a[y][k];
        for (int j = (int)s[x].size() - 1; j >= 0; j--) {
          addBeg(n + i, s[x][j]);
        }
      } else if (sz[y] <= K) {
        st[n + i] = st[x];
        nd[n + i] = nd[x];
        for (int k = 0; k < 15; k++) a[n + i][k] = a[x][k];
        for (int j = 0; j < s[y].size(); j++) {
          addEnd(n + i, s[y][j]);
        }
      } else {
        st[n + i] = st[x];
        nd[n + i] = nd[y];
        for (int k = 1; k < 15; k++) {
          a[n + i][k] = a[x][k] | a[y][k];
          for (int iii = 1; iii < k; iii++) {
            int cur = 0;
            for (int kk = 0; kk < k; kk++) {
              if (kk < iii) {
                cur = (cur << 1) | (nd[x][nd[x].size() - iii + kk] - '0');
              } else {
                cur = (cur << 1) | (st[y][kk - iii] - '0');
              }
            }
            a[n + i][k].set(cur);
          }
          if (a[n + i][k].count() == (1 << k)) res[n + i] = k;
        }
      }
    }
    printf("%d\n", res[n + i]);
  }
  return 0;
}