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>
const int K = 13;
struct node {
  int longer;
  std::bitset<1 << K> mask;
  int L, R;
  int len, val;
  friend inline node operator+(const node &a, const node &b) {
    node res;
    if (a.longer) {
      res.longer = 1;
      if (b.longer) {
        res.mask = a.mask | b.mask;
        res.L = a.L;
        res.R = b.R;
        for (int i = 1; i < K; i++)
          res.mask.set(a.R >> i | (b.L & (1 << i) - 1) << K - i);
      } else {
        res.mask = a.mask;
        res.L = a.L;
        res.R = a.R >> b.len | b.val << K - b.len;
        for (int i = 1; i <= b.len; i++)
          res.mask.set(a.R >> i | (b.val & (1 << i) - 1) << K - i);
      }
    } else {
      if (b.longer) {
        res.longer = 1;
        res.mask = b.mask;
        res.L = a.val | (b.L & (1 << K - a.len) - 1) << a.len;
        res.R = b.R;
        for (int i = 1; i <= a.len; i++)
          res.mask.set(a.val >> a.len - i | (b.L & (1 << K - i) - 1) << i);
      } else {
        int len = a.len + b.len, val = a.val | b.val << a.len;
        if (len >= K) {
          res.longer = 1;
          res.mask.reset();
          res.L = val & (1 << K) - 1;
          res.R = val >> len - K;
          for (int i = 0; i <= len - K; i++)
            res.mask.set(val >> i & (1 << K) - 1);
        } else {
          res.longer = 0;
          res.len = len;
          res.val = val;
        }
      }
    }
    return res;
  }
  void read() {
    static char s[101];
    scanf("%s", s);
    len = 0;
    while (s[len]) len++;
    if (len < K) {
      longer = 0;
      val = 0;
      for (int i = 0; i < len; i++)
        if (s[i] == '1') val |= 1 << i;
    } else {
      longer = 1;
      mask.reset();
      L = 0;
      for (int i = 0; i < K; i++)
        if (s[i] == '1') L |= 1 << i;
      mask.set(L);
      R = L;
      for (int i = 1, w = L; i <= len - K; i++) {
        w >>= 1;
        if (s[i + K - 1] == '1') w |= 1 << K - 1;
        mask.set(w);
        R = w;
      }
    }
  }
  bool check(int ans) {
    static int v[1 << K];
    for (int i = 0; i < 1 << ans; i++) v[i] = 0;
    if (longer) {
      for (int i = 0; i < 1 << K; i++)
        if (mask[i]) v[i & (1 << ans) - 1] = 1;
      for (int i = 1; i <= K - ans; i++) v[R >> i & (1 << ans) - 1] = 1;
    } else {
      for (int i = 0; i <= len - ans; i++) v[val >> i & (1 << ans) - 1] = 1;
    }
    for (int i = 0; i < 1 << ans; i++)
      if (!v[i]) return false;
    return true;
  }
  int answer() {
    int ans = K;
    while (ans && !check(ans)) ans--;
    return ans;
  }
} p[201];
int N, M;
int main() {
  scanf("%d", &N);
  for (int i = 1; i <= N; i++) p[i].read();
  scanf("%d", &M);
  for (int i = N + 1, x, y; i <= N + M; i++) {
    scanf("%d%d", &x, &y);
    p[i] = p[x] + p[y];
    printf("%d\n", p[i].answer());
  }
  return 0;
}