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.
#include <bits/stdc++.h>
using namespace std;
const int MOD = (int)1e9 + 7;
class modint {
  int v;

 public:
  modint() : v(0) {}
  modint(long long v) : v((v + MOD) % MOD) {}
  bool operator==(modint x) { return v == x.v; }
  bool operator!=(modint x) { return v != x.v; }
  modint operator+(modint x) { return v + x.v; }
  modint operator-(modint x) { return v - x.v; }
  modint operator*(modint x) { return (long long)v * x.v; }
  modint& operator+=(const modint x) { return *this = (*this + x); }
  modint& operator-=(const modint x) { return *this = (*this - x); }
  modint& operator*=(const modint x) { return *this = (*this * x); }
  int operator*() { return v; }
};
const int N_ = 105, M_ = 105;
const int L = 16;
int N, M;
bitset<(1 << L)> tb[N_ + M_];
int len[N_ + M_];
string pref[N_ + M_], suff[N_ + M_];
char tmp[105];
int main() {
  scanf("%d", &N);
  for (int i = 1; i <= N; i++) {
    scanf("%s", tmp);
    pref[i] = tmp;
    suff[i] = tmp;
    len[i] = strlen(tmp);
    tb[i].set(1);
    for (int a = 0; a < len[i]; a++) {
      int cur = 0;
      for (int b = a; b - a + 1 < L && b < len[i]; b++) {
        cur = (cur << 1) | (tmp[b] - '0');
        tb[i][cur | (1 << (b - a + 1))] = true;
      }
    }
  }
  scanf("%d", &M);
  for (int i = N + 1; i <= N + M; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    tb[i] = tb[x] | tb[y];
    len[i] = len[x] + len[y];
    pref[i] = pref[x];
    if (len[x] < L) {
      pref[i] += pref[y];
      if (pref[i].length() > L) pref[i] = pref[i].substr(0, L);
    }
    suff[i] = suff[y];
    if (len[y] < L) {
      suff[i] = suff[x] + suff[y];
      if (suff[i].length() > L)
        suff[i] = suff[i].substr(suff[i].length() - L, L);
    }
    vector<int> ml(1);
    for (int i = 0, j = (int)suff[x].size() - 1; j >= 0; i++, j--) {
      ml.push_back(ml.back() | ((suff[x][j] - '0') << i));
    }
    vector<int> mr(1);
    for (int i = 0; i < pref[y].size(); i++) {
      mr.push_back((mr.back() << 1) | (pref[y][i] - '0'));
    }
    for (int a = 1; a < ml.size(); a++) {
      for (int b = 1; a + b < L && b < mr.size(); b++) {
        tb[i].set((1 << (a + b)) | ((ml[a] << b) | mr[b]));
      }
    }
    int ans = 0;
    while (1) {
      bool good = true;
      for (int mask = 0; mask < (1 << ans) && good; mask++) {
        if (!tb[i][(1 << ans) | mask]) good = false;
      }
      if (!good) break;
      ans += 1;
    }
    ans -= 1;
    printf("%d\n", ans);
  }
  return 0;
}
