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.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
import java.math.BigInteger;
import java.io.BufferedReader;
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;
		FastScanner in = new FastScanner(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskD solver = new TaskD();
		solver.solve(1, in, out);
		out.close();
	}

	static class TaskD {
		public void solve(int testNumber, FastScanner in, PrintWriter out) {
			int n = in.nextInt();
			List<LongString> strings = new ArrayList<>();
			for (int i = 0; i < n; i++) {
				char[] s = in.next().toCharArray();
				strings.add(new LongString(s));
			}
			int m = in.nextInt();
			for (int i = 0; i < m; i++) {
				int a = in.nextInt() - 1;
				int b = in.nextInt() - 1;
				LongString l = strings.get(a);
				LongString r = strings.get(b);
				LongString s = new LongString(l, r);
				strings.add(s);
				out.println(s.bestLen);
			}
		}

		class LongString {
			char[] s;
			LongString l;
			LongString r;
			final int K = 18;
			int bestLen;
			BigInteger length;
			BitSet[] setsByLen = new BitSet[K + 1];

			LongString(char[] s) {
				this.s = s;
				length = BigInteger.valueOf(s.length);
				addAllSubstrings();
			}

			LongString(LongString l, LongString r) {
				this.l = l;
				this.r = r;
				length = l.length.add(r.length);
				bestLen = Math.max(l.bestLen, r.bestLen);

				if (bestLen == K) {
					return;
				}

				for (int len = 1; len <= K; len++) {
					setsByLen[len] = (BitSet) l.setsByLen[len].clone();
					setsByLen[len].or(r.setsByLen[len]);
				}

				for (int len = 1; len <= K; len++) {
					for (int leftLen = 1; leftLen < len; leftLen++) {
						int rightLen = len - leftLen;
						if (l.length.compareTo(BigInteger.valueOf(leftLen)) < 0) {
							continue;
						}
						if (r.length.compareTo(BigInteger.valueOf(rightLen)) < 0) {
							continue;
						}
						int mask = 0;
						BigInteger lpos = l.length.subtract(BigInteger.valueOf(leftLen));
						BigInteger rpos = BigInteger.ZERO;
						for (int i = 0; i < len; i++) {
							char c;
							if (i < leftLen) {
								c = l.charAt(lpos);
								lpos = lpos.add(BigInteger.ONE);
							} else {
								c = r.charAt(rpos);
								rpos = rpos.add(BigInteger.ONE);
							}
							mask = 2 * mask + c - '0';
						}
						setsByLen[len].set(mask);
					}
				}

				updateBest();
			}

			private char charAt(BigInteger pos) {
				if (s != null) {
					return s[pos.intValue()];
				}
				if (pos.compareTo(l.length) < 0) {
					return l.charAt(pos);
				}
				return r.charAt(pos.subtract(l.length));
			}

			private void addAllSubstrings() {
				for (int len = 1; len <= K; len++) {
					setsByLen[len] = new BitSet(len);
				}
				int n = length.intValue();
				for (int i = 0; i < n; i++) {
					int mask = 0;
					int len = 0;
					for (int j = i; j < n; j++) {
						mask = 2 * mask + charAt(BigInteger.valueOf(j)) - '0';
						++len;
						if (len <= K) {
							setsByLen[len].set(mask);
						}
					}
				}
				updateBest();
			}

			private void updateBest() {
				bestLen = 0;
				for (int len = K; len > 0; len--) {
					boolean ok = true;
					for (int mask = 0; mask < 1 << len; mask++) {
						if (!setsByLen[len].get(mask)) {
							ok = false;
							break;
						}
					}
					if (ok) {
						bestLen = len;
						break;
					}
				}
			}

		}

	}

	static class FastScanner {
		private BufferedReader in;
		private StringTokenizer st;

		public FastScanner(InputStream stream) {
			in = new BufferedReader(new InputStreamReader(stream));
		}

		public String next() {
			while (st == null || !st.hasMoreTokens()) {
				try {
					String rl = in.readLine();
					if (rl == null) {
						return null;
					}
					st = new StringTokenizer(rl);
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return st.nextToken();
		}

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

	}
}

