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;
const int MAXL = 12;
const int MAXN = 210;
struct Elem {
  int f, s;
  string txt;
  pair<bool, int> go[MAXL];
  Elem() { f = s = -1; }
  void Reset() {
    for (int i = 0; i < MAXL; ++i) go[i].second = -1;
  }
};
int n, m;
Elem in[MAXN];
bool StartsWith(const string& s, const string& with) {
  if (((int)(with).size()) > ((int)(s).size())) return false;
  for (int i = 0; i < ((int)(with).size()); ++i)
    if (s[i] != with[i]) return false;
  return true;
}
string AsList(int w, int len) {
  string res = "";
  for (int i = 0; i < len; ++i) res.push_back((w & (1 << i)) ? '1' : '0');
  return res;
}
vector<array<int, 2>> Automaton(const string& w) {
  vector<array<int, 2>> go(((int)(w).size()) + 1);
  go[0][0] = (w[0] == '0' ? 1 : 0);
  go[0][1] = (w[0] == '1' ? 1 : 0);
  for (int i = 1; i <= ((int)(w).size()); ++i) {
    string t = w.substr(0, i) + '0';
    while (((int)(t).size()) > 0 && !StartsWith(w, t)) t.erase(t.begin());
    go[i][0] = ((int)(t).size());
    t = w.substr(0, i) + '1';
    while (((int)(t).size()) > 0 && !StartsWith(w, t)) t.erase(t.begin());
    go[i][1] = ((int)(t).size());
  }
  return go;
}
vector<array<int, 2>> aut;
void SetEnd(pair<bool, int>& w) {
  if (w.second + 1 == ((int)(aut).size())) w.first = true;
}
pair<bool, int> Search(int idx, int start) {
  auto& e = in[idx];
  if (e.go[start].second >= 0) return e.go[start];
  if (e.f != -1) {
    pair<bool, int> res = Search(e.f, start);
    if (res.first) return e.go[start] = res;
    res = Search(e.s, res.second);
    return e.go[start] = res;
  } else {
    pair<bool, int> res(false, start);
    SetEnd(res);
    for (int i = 0; i < ((int)(e.txt).size()); ++i) {
      res.second = aut[res.second][e.txt[i] - '0'];
      SetEnd(res);
    }
    return e.go[start] = res;
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin >> n;
  for (int i = 0; i < n; ++i) cin >> in[i].txt;
  cin >> m;
  for (int i = n; i < n + m; ++i)
    cin >> in[i].f >> in[i].s, --in[i].f, --in[i].s;
  for (int i = n; i < n + m; ++i) {
    int len;
    for (len = 1; len < MAXL; ++len) {
      bool ok = true;
      for (int msk = 0; msk < (1 << len); ++msk) {
        for (int j = 0; j <= i; ++j) in[j].Reset();
        aut = Automaton(AsList(msk, len));
        if (!Search(i, 0).first) {
          ok = false;
          break;
        }
      }
      if (!ok) break;
    }
    cout << len - 1 << '\n';
  }
  return 0;
}