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;
template <class T>
inline T bigmod(T p, T e, T M) {
  long long ret = 1;
  for (; e > 0; e >>= 1) {
    if (e & 1) ret = (ret * p) % M;
    p = (p * p) % M;
  }
  return (T)ret;
}
template <class T>
inline T gcd(T a, T b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
template <class T>
inline T modinverse(T a, T M) {
  return bigmod(a, M - 2, M);
}
template <class T>
inline T lcm(T a, T b) {
  a = abs(a);
  b = abs(b);
  return (a / gcd(a, b)) * b;
}
template <class T, class X>
inline bool getbit(T a, X i) {
  T t = 1;
  return ((a & (t << i)) > 0);
}
template <class T, class X>
inline T setbit(T a, X i) {
  T t = 1;
  return (a | (t << i));
}
template <class T, class X>
inline T resetbit(T a, X i) {
  T t = 1;
  return (a & (~(t << i)));
}
inline long long getnum() {
  char c = getchar();
  long long num, sign = 1;
  for (; c < '0' || c > '9'; c = getchar())
    if (c == '-') sign = -1;
  for (num = 0; c >= '0' && c <= '9';) {
    c -= '0';
    num = num * 10 + c;
    c = getchar();
  }
  return num * sign;
}
inline long long power(long long a, long long b) {
  long long multiply = 1;
  for (int i = (0); i < (b); i++) {
    multiply *= a;
  }
  return multiply;
}
int n, m;
string s[205];
map<string, bool> bins[205];
int cnt[205][105], maxLen[205];
string l[205], r[205];
int getMax(int idx) {
  for (int i = 1; i < 10; i++) {
    if (cnt[idx][i] != (1 << i)) return i - 1;
  }
}
void copy(int from, int to) {
  for (auto it : bins[from]) {
    if (bins[to].find(it.first) == bins[to].end()) {
      bins[to].insert(it);
      cnt[to][(int)it.first.size()]++;
    }
  }
}
string get(string now, bool flag) {
  string ret = "";
  if (!flag)
    for (int j = (0); j < (min((int)now.size(), 9)); j++) ret += now[j];
  if (flag)
    for (int j = (max(0, (int)now.size() - 9)); j < (now.size()); j++)
      ret += now[j];
  return ret;
}
int main() {
  int test, cases = 1;
  cin >> n;
  for (int i = (0); i < (n); i++) cin >> s[i];
  for (int i = (0); i < (n); i++) {
    for (int j = (0); j < (min((int)s[i].size(), 9)); j++) l[i] += s[i][j];
    for (int j = (max(0, (int)s[i].size() - 9)); j < (s[i].size()); j++)
      r[i] += s[i][j];
  }
  for (int i = (0); i < (n); i++) {
    for (int j = (0); j < (s[i].size()); j++) {
      string t = "";
      for (int k = (j); k < (s[i].size()); k++) {
        t += s[i][k];
        if (bins[i].find(t) == bins[i].end()) {
          bins[i][t] = true;
          cnt[i][(int)t.size()]++;
        }
      }
    }
  }
  for (int i = (0); i < (n); i++) maxLen[i] = getMax(i);
  cin >> m;
  int x, y;
  for (int i = (0); i < (m); i++) {
    cin >> x >> y;
    x--, y--;
    string now = r[x] + l[y];
    l[n + i] = l[x];
    for (int j = 0; l[n + i].size() < 9 && j < l[y].size(); j++)
      l[n + i] += l[y][j];
    r[n + i] = r[y];
    for (int j = (int)r[x].size() - 1; r[n + i].size() < 9 && j >= 0; j--)
      r[n + i] = r[x][j] + r[n + i];
    copy(x, n + i);
    copy(y, n + i);
    for (int j = (0); j < (now.size()); j++) {
      string t = "";
      for (int k = (j); k < (now.size()); k++) {
        t += now[k];
        if (bins[n + i].find(t) == bins[n + i].end()) {
          bins[n + i][t] = true;
          cnt[n + i][(int)t.size()]++;
        }
      }
    }
    maxLen[n + i] = getMax(n + i);
    cout << maxLen[n + i] << "\n";
  }
  return 0;
}
