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.OutputStream;
import java.io.PrintWriter;
import java.io.BufferedWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.util.ArrayList;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.util.BitSet;
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;
        InputReader in = new InputReader(inputStream);
        OutputWriter out = new OutputWriter(outputStream);
        TaskD solver = new TaskD();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskD {
        final static int MAX_LENGTH = 20;
        final static int HUNDRED = 100;
        final static int MAX_S = 4 * HUNDRED * HUNDRED;

        public void solve(int testNumber, InputReader in, OutputWriter out) {
            int n = in.readInt();
            ArrayList<S> al = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                S s = new S();
                s.init(in.next());
                al.add(s);
            }
            int m = in.readInt();
            for (int op = 0; op < m; op++) {
                int aIndex = in.readInt() - 1;
                int bIndex = in.readInt() - 1;
                S ab = new S();
                ab.copy(al.get(aIndex).memories);
                ab.copy(al.get(bIndex).memories);
                String a = al.get(aIndex).s;
                String b = al.get(bIndex).s;
                ab.init(a + b);
                out.printLine(ab.getMax());
                al.add(ab);
            }
        }

        class S {
            BitSet[] memories = new BitSet[MAX_LENGTH];
            String s;

            public S() {
                for (int length = 1; length <= memories.length; length++) {
                    int size = 1 << length;
                    memories[length - 1] = new BitSet(size);
                }
            }

            void init(String s) {
                if (s.length() > MAX_S) {
                    s = s.substring(0, MAX_S / 2) + s.substring(s.length() - MAX_S / 2);
                }
                this.s = s;
                for (int length = 1; length <= memories.length; length++) {
                    BitSet bitSet = memories[length - 1];
                    for (int start = 0; start + length <= s.length(); start++) { // TODO check
                        if (start < HUNDRED || start >= s.length() - HUNDRED) {
                            int val = 0;
                            for (int i = start; i < start + length; i++) {
                                val <<= 1;
                                if (s.charAt(i) == '1') {
                                    val++;
                                }
                            }
                            bitSet.set(val, true);
                        }
                    }
                }
            }

            void copy(BitSet[] otherMemories) {
                for (int length = 1; length <= memories.length; length++) {
                    memories[length - 1].or(otherMemories[length - 1]);
                }
            }

            int getMax() {
                for (int length = 1; length <= memories.length; length++) {
                    BitSet bitSet = memories[length - 1];
                    if (bitSet.cardinality() != (1 << length)) {
                        return length - 1;
                    }
                }
                return memories.length;
            }
        }
    }
    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private InputReader.SpaceCharFilter filter;

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

        public 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++];
        }

        public int readInt() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

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

        public boolean isSpaceChar(int c) {
            if (filter != null) {
                return filter.isSpaceChar(c);
            }
            return isWhitespace(c);
        }

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

        public String next() {
            return readString();
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);
        }
    }
    static class OutputWriter {
        private final PrintWriter writer;

        public OutputWriter(OutputStream outputStream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }

        public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }

        public void close() {
            writer.close();
        }

        public void printLine(int i) {
            writer.println(i);
        }
    }
}

