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;
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
  cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
  const char* comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << " : " << arg1 << " | ";
  __f(comma + 1, args...);
}
template <class X>
void print(X x) {
  cout << x << endl;
  exit(0);
}
int value(string s) {
  int x = 0;
  int pw = 1;
  for (int i = 0; i < s.size(); i++) {
    x += pw * (s[i] - 48);
    pw *= 2;
  }
  return x;
}
vector<vector<bool> > find(string& second) {
  vector<vector<bool> > final;
  for (int k = 0; k <= 9; k++) {
    vector<bool> pres(1 << k, false);
    for (int i = 0; i <= (int)second.size() - k; i++) {
      int x = value(second.substr(i, k));
      pres[x] = true;
    }
    final.push_back(pres);
  }
  return final;
}
vector<bool> mix(vector<bool>& a, vector<bool>& b) {
  vector<bool> to_return((int)a.size(), false);
  for (int i = 0; i < a.size(); i++) to_return[i] = a[i] or b[i];
  return to_return;
}
int main() {
  ios_base::sync_with_stdio(0);
  int n;
  cin >> n;
  string s[n + 1];
  vector<string> first, last;
  first.push_back("0");
  last = first;
  vector<vector<vector<bool> > > check;
  check.push_back(vector<vector<bool> >());
  vector<int> L;
  L.push_back(0);
  for (int i = 1; i <= n; i++) {
    cin >> s[i];
    int l = s[i].size();
    if (l > 9)
      first.push_back(s[i].substr(0, 9)), last.push_back(s[i].substr(l - 9, 9));
    else
      first.push_back(s[i]), last.push_back(s[i]);
    vector<vector<bool> > X = find(s[i]);
    check.push_back(X);
    L.push_back((int)(s[i].size()));
  }
  int m;
  cin >> m;
  pair<int, int> b[m];
  for (int i = 0; i < m; i++) cin >> b[i].first >> b[i].second;
  int ct = n + 1;
  for (auto x : b) {
    int v1 = x.first;
    int v2 = x.second;
    string sfx = last[v1];
    string pfx = first[v2];
    string extra = sfx + pfx;
    L.push_back(L[v1] + L[v2]);
    if (L.back() > 1000) L.back() = 1000;
    if (L[v2] >= 9) {
      last.push_back(last[v2]);
      __f("last.back().size()", last.back().size());
    } else {
      if (L.back() >= 9) {
        int z = extra.size();
        last.push_back(extra.substr(z - 9, 9));
        __f("last.back().size()", last.back().size());
      } else {
        last.push_back(extra);
        __f("last.back().size()", last.back().size());
      }
    }
    if (L[v1] >= 9)
      first.push_back(first[v1]);
    else {
      if (L.back() >= 9)
        first.push_back(extra.substr(0, 9));
      else
        first.push_back(extra);
    }
    ct++;
    vector<vector<bool> > bitmask;
    vector<vector<bool> > add = find(extra);
    for (int k = 0; k <= 9; k++) {
      vector<bool> BIT((1 >> k), false);
      vector<bool> bit1 = check[v1][k], bit2 = check[v2][k];
      BIT = mix(bit1, bit2);
      BIT = mix(add[k], BIT);
      bitmask.push_back(BIT);
    }
    check.push_back(bitmask);
    for (int k = 9; k >= 0; k--) {
      bool ans = true;
      for (int i = 0; i < (1 << k); i++)
        if (bitmask[k][i] == false) ans = false;
      if (ans) {
        cout << k << endl;
        __f("ct", ct);
        break;
      }
    }
  }
  return 0;
}