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>
#pragma GCC diagnostic ignored "-Wunused-result"
#pragma GCC diagnostic ignored "-Wunused-function"
using namespace std;
namespace {
namespace shik {
template <class T>
void _R(T &x) {
  cin >> x;
}
void _R(int &x) { scanf("%d", &x); }
void _R(int64_t &x) { scanf("%" SCNd64, &x); }
void _R(double &x) { scanf("%lf", &x); }
void _R(char &x) { scanf(" %c", &x); }
void _R(char *x) { scanf("%s", x); }
void R() {}
template <class T, class... U>
void R(T &head, U &...tail) {
  _R(head);
  R(tail...);
}
template <class T>
void _W(const T &x) {
  cout << x;
}
void _W(const int &x) { printf("%d", x); }
void _W(const int64_t &x) { printf("%" PRId64, x); }
void _W(const double &x) { printf("%.16f", x); }
void _W(const char &x) { putchar(x); }
void _W(const char *x) { printf("%s", x); }
template <class T>
void _W(const vector<T> &x) {
  for (auto i = x.begin(); i != x.end(); _W(*i++))
    if (i != x.cbegin()) putchar(' ');
}
void W() {}
template <class T, class... U>
void W(const T &head, const U &...tail) {
  _W(head);
  putchar(sizeof...(tail) ? ' ' : '\n');
  W(tail...);
}
template <class T, class F = less<T>>
void sort_uniq(vector<T> &v, F f = F()) {
  sort(begin(v), end(v), f);
  v.resize(unique(begin(v), end(v)) - begin(v));
}
template <class T>
inline T bit(T x, int i) {
  return (x >> i) & 1;
}
template <class T>
inline bool chkmax(T &a, const T &b) {
  return b > a ? a = b, true : false;
}
template <class T>
inline bool chkmin(T &a, const T &b) {
  return b < a ? a = b, true : false;
}
template <class T>
using MaxHeap = priority_queue<T>;
template <class T>
using MinHeap = priority_queue<T, vector<T>, greater<T>>;
const int L = 14;
struct P {
  set<uint32_t> st[L + 1];
  string l, r;
  void add(const string &s) {
    for (int i = 0; i < int(((int)(s).size())); i++) {
      uint32_t x = 0;
      for (int j = (1); j <= int(L); j++) {
        if (i + j > ((int)(s).size())) break;
        x = x * 2 + (s[i + j - 1] - '0');
        st[j].insert(x);
      }
    }
  }
  P() {}
  P(string s) {
    if (((int)(s).size()) <= L) {
      l = r = s;
    } else {
      l = s.substr(0, L);
      r = s.substr(((int)(s).size()) - L);
    }
    st[0].insert(0);
    add(s);
  }
  int lv() {
    int x = 0;
    while (x < L && ((int)(st[x]).size()) == (1 << x)) x++;
    assert(x != L);
    return x - 1;
  }
};
P operator+(const P &a, const P &b) {
  P c;
  c.l = (a.l + b.l);
  c.r = (a.r + b.r);
  if (((int)(c.l).size()) > L) c.l = c.l.substr(0, L);
  if (((int)(c.r).size()) > L) c.r = c.r.substr(((int)(c.r).size()) - L);
  for (int i = 0; i < int(L); i++) {
    c.st[i].insert(begin(a.st[i]), end(a.st[i]));
    c.st[i].insert(begin(b.st[i]), end(b.st[i]));
  }
  c.add(a.r + b.l);
  return c;
}
const int N = 210;
int n, m;
string s[N];
P p[N];
void main() {
  R(n);
  for (int i = (1); i <= int(n); i++) R(s[i]);
  for (int i = (1); i <= int(n); i++) p[i] = s[i];
  R(m);
  for (int i = (1); i <= int(m); i++) {
    int a, b;
    R(a, b);
    p[n + i] = p[a] + p[b];
    int ans = p[n + i].lv();
    W(ans);
  }
}
}  // namespace shik
}  // namespace
int main() {
  shik::main();
  return 0;
}