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 JAVA):

Solution:
//package com.company;

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        MyScanner sc = new MyScanner(System.in);
        PrintWriter pw = new PrintWriter(System.out);
        long start = System.currentTimeMillis();
        HugeStrings.solve(sc, pw);
        long end = System.currentTimeMillis();
//        pw.println("Used time " + (end - start) + "ms.");
        pw.close();
    }


    //http://codeforces.com/contest/868/problem/D
    public static class HugeStrings {
        // One important feature of this problem is that the answer is small for each query. Suppose the largest
        // possible answer is X. Then, whenever we merge two strings, the number of new strings created with length = X
        // is at most X. In total we create at most 100 * X such strings.
        // We have the inequality 2^{X} <= 100 * X + 100 ----> X <= 11; We can just "almost" brute force the solution.
        static int L = 12;
        static int n, m;
        static String[] prefix;
        static String[] suffix;
        static Set<String>[][] cnt;
        static String[] original;
        static int[] len;

        public static void solve(MyScanner sc, PrintWriter pw) throws IOException {
            n = sc.nextInt();
            original = new String[n];
            for (int i = 0; i < n; i++) {
                original[i] = sc.next();
            }
            m = sc.nextInt();
            prefix = new String[n + m];
            suffix = new String[n + m];
            len = new int[n + m];
            cnt = new Set[n + m][L + 1];
            for (int i = 0; i < cnt.length; i++) {
                for (int j = 0; j < cnt[i].length; j++) {
                    cnt[i][j] = new HashSet<>();
                }
            }
            for (int i = 0; i < n; i++) {
                len[i] = original[i].length();
                prefix[i] = original[i].substring(0, Math.min(L, len[i]));
                suffix[i] = original[i].substring(Math.max(0, len[i] - L), len[i]);
                for (int j = 0; j < len[i]; j++) {
                    for (int k = j + 1; k <= len[i]; k++) {
                        if (k - j > L) break;
                        cnt[i][k - j].add(original[i].substring(j, k));
                    }
                }
            }
            for (int i = 0; i < m; i++) {
                int a = sc.nextInt() - 1;
                int b = sc.nextInt() - 1;
                if (len[a] > L && len[b] > L) {
                    len[n + i] = L + 1;
                    prefix[n + i] = prefix[a];
                    suffix[n + i] = suffix[b];
                } else if (len[a] > L && len[b] <= L) {
                    len[n + i] = L + 1;
                    prefix[n + i] = prefix[a];
                    String str = (suffix[a] + suffix[b]);
                    suffix[n + i] = str.substring(str.length() - L, str.length());
                } else if (len[a] <= L && len[b] > L) {
                    len[n + i] = L + 1;
                    suffix[n + i] = suffix[b];
                    String str = (prefix[a] + prefix[b]);
                    prefix[n + i] = str.substring(0, L);
                } else {
                    len[n + i] = len[a] + len[b];
                    String str = (prefix[a] + prefix[b]);
                    prefix[n + i] = str.substring(0, Math.min(L, str.length()));
                    str = (suffix[a] + suffix[b]);
                    suffix[n + i] = str.substring(Math.max(0, str.length() - L), str.length());
                }
                for (int j = 1; j <= L; j++) {
                    cnt[n + i][j].addAll(cnt[a][j]);
                    cnt[n + i][j].addAll(cnt[b][j]);
                }
                for (int j = 1; j <= suffix[a].length(); j++) {
                    for (int k = 1; k <= prefix[b].length(); k++) {
                        if (j + k > L) break;
                        String newstr = suffix[a].substring(suffix[a].length() -j, suffix[a].length()) +
                                prefix[b].substring(0, k);
                        cnt[n + i][j + k].add(newstr);
                    }
                }
                long mask = 1L;
                for (int j = 1; j <= L; j++) {
                    mask <<= 1L;
                    if (cnt[n + i][j].size() < mask) {
                        pw.println(j - 1);
                        break;
                    }

                }
            }
        }
    }

    static class MyScanner {
        StringTokenizer st;
        BufferedReader br;

        public MyScanner(InputStream s){  br = new BufferedReader(new InputStreamReader(s));}

        public MyScanner(FileReader s) throws FileNotFoundException {br = new BufferedReader(s);}

        public String next() throws IOException
        {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

        public int nextInt() throws IOException {return Integer.parseInt(next());}

        public long nextLong() throws IOException {return Long.parseLong(next());}

        public String nextLine() throws IOException {return br.readLine();}

        public double nextDouble() throws IOException { return Double.parseDouble(next()); }

        public boolean ready() throws IOException {return br.ready();}
    }
}