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;
struct word {
  int len;
  bool head[30];
  bool tail[30];
  set<int> s[30];
};
bool done, combin[60], combin2[60], combin3[60];
char s[101][101];
int n, m, a, b, num, ans;
word w[201];
set<int>::iterator it;
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%s", s[i]);
    w[i].len = strlen(s[i]);
    for (int j = 0; j < w[i].len; j++) {
      num = 0;
      for (int k = j; k < min(w[i].len, j + 29); k++) {
        num = num * 2 + s[i][k] - '0';
        w[i].s[k - j + 1].insert(num);
      }
    }
    if (w[i].len < 30) {
      for (int j = 0; j < w[i].len; j++) {
        w[i].head[j] = s[i][j] - '0';
        w[i].tail[j] = s[i][j] - '0';
      }
    } else {
      for (int j = 0; j < 29; j++) w[i].head[j] = s[i][j] - '0';
      for (int j = w[i].len - 29; j < w[i].len; j++)
        w[i].tail[j - (w[i].len - 29)] = s[i][j] - '0';
      w[i].len = 29;
    }
  }
  scanf("%d", &m);
  for (int i = n + 1; i <= n + m; i++) {
    scanf("%d %d", &a, &b);
    w[i].len = w[a].len + w[b].len;
    for (int j = 0; j < w[a].len; j++) combin[j] = w[a].tail[j];
    for (int j = w[a].len; j < w[i].len; j++)
      combin[j] = w[b].head[j - w[a].len];
    for (int j = 1; j <= 29; j++) {
      w[i].s[j] = w[a].s[j];
      if (a != b) {
        for (it = w[b].s[j].begin(); it != w[b].s[j].end(); it++)
          w[i].s[j].insert(*it);
      }
    }
    for (int j = 0; j < w[i].len; j++) {
      num = 0;
      for (int k = j; k < min(w[i].len, j + 29); k++) {
        num = num * 2 + combin[k];
        w[i].s[k - j + 1].insert(num);
      }
    }
    for (int j = 0; j < w[a].len; j++) {
      combin2[j] = w[a].head[j];
      combin3[j] = w[a].tail[j];
    }
    for (int j = w[a].len; j < w[i].len; j++) {
      combin2[j] = w[b].head[j - w[a].len];
      combin3[j] = w[b].tail[j - w[a].len];
    }
    if (w[i].len < 30) {
      for (int j = 0; j < w[i].len; j++) {
        w[i].head[j] = combin2[j];
        w[i].tail[j] = combin3[j];
      }
    } else {
      for (int j = 0; j < 29; j++) w[i].head[j] = combin2[j];
      for (int j = w[i].len - 29; j < w[i].len; j++)
        w[i].tail[j - (w[i].len - 29)] = combin3[j];
      w[i].len = 29;
    }
    ans = 0;
    while (w[i].s[ans + 1].size() == 1 << (ans + 1)) ans++;
    printf("%d\n", ans);
  }
  return 0;
}