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.
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.HashSet;
import java.util.AbstractCollection;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastScanner in = new FastScanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        D868 solver = new D868();
        solver.solve(1, in, out);
        out.close();
    }

    static class D868 {
        int magic = 15;
        int N;
        int M;

        HashSet<String>[] substrings(String ss) {
            int L = ss.length();
            HashSet<String>[] res = new HashSet[magic + 1];
            for (int i = 0; i < magic + 1; i++)
                res[i] = new HashSet<>();
            for (int i = 0; i < L; i++) {
                for (int j = i + 1; j <= L; j++) {
                    if (j - i > magic) continue;
                    res[j - i].add(ss.substring(i, j));
                }
            }
            return res;
        }

        String front(String s) {
            if (s.length() >= 99)
                return s.substring(0, 99);
            return new String(s);
        }

        String back(String s) {
            if (s.length() <= 99)
                return new String(s);
            return s.substring(s.length() - 99 - 1);
        }

        public void solve(int testNumber, FastScanner s, PrintWriter out) {
            N = s.nextInt();
            ZString[] strings = new ZString[N + 101];
            int ind = 0;
            for (; ind < N; ind++) {
                strings[ind] = new ZString(s.next());
//            out.println(strings[ind].maxK);
            }
//        out.println("===============");
            M = s.nextInt();
            for (; ind < N + M; ind++) {
                int u = s.nextInt() - 1, v = s.nextInt() - 1;
                strings[ind] = new ZString(strings[u], strings[v]);
                out.println(strings[ind].maxK);
            }
        }

        class ZString {
            HashSet<String>[] in = new HashSet[magic + 1];
            String first99;
            String last99;
            int maxK;
            boolean baby;

            public ZString(String init) {
                baby = init.length() <= 99;
                in = substrings(init);
                first99 = front(init);
                last99 = back(init);
//            int[] v = new int[12];
//            for (int i = 0; i < 12; i++)
//                v[i] = in[i].size();
//            System.out.println(Arrays.toString(v));
                calc();
            }

            public ZString(ZString L, ZString R) {
                String fresh = L.last99 + R.first99;
                in = substrings(fresh);
                for (int i = 1; i < magic; i++) {
                    in[i].addAll(L.in[i]);
                    in[i].addAll(R.in[i]);
                }

                if (L.baby && R.baby) {
                    baby = (L.first99.length() + R.first99.length()) <= 99;
                    first99 = front(fresh);
                    last99 = back(fresh);
                } else if (L.baby) {
                    first99 = front(L.first99 + R.first99);
                    last99 = new String(R.last99);
                    baby = false;
                } else if (R.baby) {
                    first99 = new String(L.first99);
                    last99 = back(L.last99 + R.first99);
                    baby = false;
                } else {
                    first99 = new String(L.first99);
                    last99 = new String(R.last99);
                    baby = false;
                }
                calc();
            }

            void calc() {
                maxK = 0;
                for (int i = 1; i < magic + 1; i++) {
                    if (in[i].size() != (1 << i)) break;
                    maxK = i;
                }
            }

        }

    }

    static class FastScanner {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;

        public FastScanner(InputStream stream) {
            this.stream = stream;
        }

        int read() {
            if (numChars == -1)
                throw new InputMismatchException();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

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

        public String next() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }

    }
}

