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 max_len1 = 16;
const int max_len = 16;
bool mask[210][max_len + 1][1 << max_len];
string pref[210];
string suf[210];
int sz[210];
int main() {
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  for (int k = 0; k < (int)(n); ++k) {
    string s;
    cin >> s;
    sz[k] = s.size();
    mask[k][0][0] = true;
    for (int l = 0; l < (int)(max_len1 + 1); ++l) {
      if (l == 0) {
        continue;
      }
      for (int a = 0; a < (int)(1 << l); ++a) {
        for (int i = 0; i < (int)(s.size() - l + 1); ++i) {
          bool ok = true;
          for (int j = 0; j < (int)(l); ++j) {
            if (s[i + l - 1 - j] != '0' + bool(a & (1 << j))) {
              ok = false;
            }
          }
          if (ok) {
            mask[k][l][a] = true;
            break;
          }
        }
      }
    }
    for (int i = 0; i < (int)(min(max_len, int(s.size()))); ++i) {
      pref[k] += s[i];
    }
    for (int i = 0; i < (int)(min(max_len, int(s.size()))); ++i) {
      suf[k] += s[s.size() - min(max_len, int(s.size())) + i];
    }
  }
  int m;
  cin >> m;
  for (int q = 0; q < (int)(m); ++q) {
    int k = n + q;
    int x, y;
    cin >> x >> y;
    --x;
    --y;
    sz[k] = min(100000, sz[x] + sz[y]);
    mask[k][0][0] = true;
    int ans = 0;
    for (int l = 0; l < (int)(max_len + 1); ++l) {
      if (l == 0) {
        continue;
      }
      for (int a = 0; a < (int)(1 << l); ++a) {
        if (mask[x][l][a] || mask[y][l][a]) {
          mask[k][l][a] = true;
        }
      }
      for (int i = 0; i < (int)(min(l, int(pref[y].size()) + 1)); ++i) {
        if (i == 0 || l - i > int(suf[x].size())) {
          continue;
        }
        int msk = 0;
        for (int j = 0; j < (int)(l - i); ++j) {
          msk <<= 1;
          msk += suf[x][int(suf[x].size()) - l + i + j] == '1';
        }
        for (int j = 0; j < (int)(i); ++j) {
          msk <<= 1;
          msk += pref[y][j] == '1';
        }
        mask[k][l][msk] = true;
      }
      bool ok = true;
      for (int a = 0; a < (int)(1 << l); ++a) {
        if (!mask[k][l][a]) {
          ok = false;
        }
      }
      if (ok) {
        ans = l;
      }
    }
    for (int i = 0; i < (int)(pref[x].size()); ++i) {
      if (pref[k].size() == max_len) {
        break;
      }
      pref[k] += pref[x][i];
    }
    for (int i = 0; i < (int)(pref[y].size()); ++i) {
      if (pref[k].size() == max_len) {
        break;
      }
      pref[k] += pref[y][i];
    }
    if (suf[y].size() < max_len) {
      for (int i = 0; i < (int)(max_len - int(suf[y].size())); ++i) {
        if (int(suf[x].size()) - max_len + int(suf[y].size()) + i < 0) {
          continue;
        }
        suf[k] += suf[x][int(suf[x].size()) - max_len + int(suf[y].size()) + i];
      }
    }
    for (int i = 0; i < (int)(suf[y].size()); ++i) {
      if (suf[k].size() == max_len) {
        break;
      }
      suf[k] += suf[y][i];
    }
    cout << ans << endl;
  }
  return 0;
}