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;
int makeNumber(const string &ss, int p, int n) {
  int j, m = 0;
  for (j = 0; j < n; j++) m = 2 * m + (ss[p + j] - '0');
  return m;
}
struct String {
  string pf, sf, wh;
  set<int> st[10];
  String(const string &bf) {
    pf = "";
    sf = "";
    wh = bf;
    for (int i = 1; i <= 10; i++)
      for (int j = 0; j < (int)(bf).size() - i + 1; j++)
        st[i - 1].insert(makeNumber(bf, j, i));
  }
  String(const String &s1, const String &s2) {
    const string &z1 = s1.getSuffix();
    const string &z2 = s2.getPrefix();
    string zz = z1 + z2;
    for (int i = 1; i <= 10; i++) {
      st[i - 1] = s1.st[i - 1];
      st[i - 1].insert(s2.st[i - 1].begin(), s2.st[i - 1].end());
    }
    for (int i = 2; i <= 10; i++)
      for (int j = 0; j < (int)(zz).size() - i + 1; j++)
        if (j < (int)(z1).size() && j + i - 1 >= (int)(z1).size())
          st[i - 1].insert(makeNumber(zz, j, i));
    if (s1.wh == "")
      pf = s1.pf;
    else if (s2.wh == "")
      pf = s1.wh + s2.pf;
    else
      pf = s1.wh + s2.wh;
    if (s2.wh == "")
      sf = s2.sf;
    else if (s1.wh == "")
      sf = s1.sf + s2.wh;
    else
      sf = s1.wh + s2.wh;
    if (s1.wh != "" && s2.wh != "") {
      wh = s1.wh + s2.wh;
      if ((int)(wh).size() > 30)
        wh = "";
      else {
        pf = "";
        sf = "";
      }
    } else
      wh = "";
    if ((int)(pf).size() > 30) pf = pf.substr(0, 30);
    if ((int)(sf).size() > 30) sf = sf.substr((int)(sf).size() - 30);
  }
  const string &getPrefix() const { return pf == "" ? wh : pf; }
  const string &getSuffix() const { return sf == "" ? wh : sf; }
  int getAnswer() const {
    for (int i = 10; i >= 1; i--)
      if ((int)(st[i - 1]).size() == (1 << i)) return i;
    return 0;
  }
};
int main() {
  char bf[108];
  int i, a, b, S, Q;
  vector<String> ss;
  scanf("%d", &S);
  for (i = 0; i < S; i++) {
    scanf("%s", bf);
    ss.push_back(String(bf));
  }
  scanf("%d", &Q);
  while (Q--) {
    scanf("%d %d", &a, &b);
    ss.push_back(String(ss[a - 1], ss[b - 1]));
    printf("%d\n", ss.back().getAnswer());
  }
  return 0;
}
