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;
vector<int> create(int k) {
  if (k == 0) return {0};
  vector<int> arr1 = create(k - 1), arr2 = arr1;
  for (auto& x : arr1) x = 2 * x;
  for (auto& x : arr2) x = 2 * x + 1;
  for (auto& x : arr2) arr1.push_back(x);
  return arr1;
}
vector<int> func(vector<string> in, int k, const vector<pair<int, int>>& Q) {
  int n = in.size();
  vector<int> all = create(k);
  vector<vector<bool>> arr(n + Q.size(), vector<bool>(all.size(), false));
  for (int i = 0; i < int(n); ++i)
    if ((int)in[i].size() >= k) {
      int curr = 0;
      for (int t = 0; t < int(k); ++t) curr = 2 * curr + in[i][t] - '0';
      arr[i][curr] = true;
      for (int t = k; t < int(in[i].size()); ++t)
        arr[i][curr = (2 * curr + in[i][t] - '0') % (1 << k)] = true;
    }
  for (int p = 0; p < int(Q.size()); ++p) {
    int x = Q[p].first, y = Q[p].second;
    vector<bool>& res = arr[n + p];
    for (int i = 0; i < int(res.size()); ++i) res[i] = arr[x][i] || arr[y][i];
    in.push_back("");
    string& adding = in.back();
    string save;
    for (auto& a : in[x]) adding.push_back(a);
    for (auto& a : in[y]) adding.push_back(a);
    while ((int)save.size() < k && (int)adding.size() > 0)
      save.push_back(adding.back()), adding.pop_back();
    while ((int)adding.size() > k) adding.pop_back();
    while ((int)save.size() > 0) adding.push_back(save.back()), save.pop_back();
    int i1 = max(0, int(in[x].size() - k + 1)), i2 = k - in[x].size() + i1 - 1;
    if (i1 >= int(in[x].size()) || i2 >= int(in[y].size())) continue;
    int curr = 0;
    for (int t = i1; t < int(in[x].size()); ++t)
      curr = 2 * curr + in[x][t] - '0';
    for (int t = 0; t < int(i2); ++t) curr = 2 * curr + in[y][t] - '0';
    while (i1 < (int)in[x].size() && i2 < (int)in[y].size()) {
      res[curr = (2 * curr + in[y][i2] - '0') % (1 << k)] = true;
      ++i1, ++i2;
    }
  }
  vector<int> ret(Q.size());
  for (int i = n; i < int(arr.size()); ++i) {
    bool b = true;
    for (auto x : arr[i])
      if (!x) {
        b = false;
        break;
      }
    ret[i - n] = b;
  }
  return ret;
}
int main() {
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  vector<string> arr(n);
  for (auto& x : arr) cin >> x;
  int m;
  cin >> m;
  vector<pair<int, int>> Q(m);
  for (auto& p : Q) cin >> p.first >> p.second, --p.first, --p.second;
  vector<int> res(m, 0);
  for (int i = 1; i < int(11); ++i) {
    vector<int> temp = func(arr, i, Q);
    for (int k = 0; k < int(res.size()); ++k)
      if (res[k] == i - 1 && temp[k]) res[k] = i;
  }
  for (auto& x : res) cout << x << endl;
  return 0;
}
