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.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskC solver = new TaskC();
		solver.solve(1, in, out);
		out.close();
	}

	static class TaskC {
		int Max = 12;

		public class StringPermutation {
			String StartPart, EndPart;
			boolean[][] Exist = new boolean[Max + 1][];
			int k = 0;

			private void CreateExist() {
				for (int i = 1; i <= Max; i++) {
					Exist[i] = new boolean[1 << i];
				}
			}

			private void UpdateMaxK() {
				boolean possible = true;
				while (possible) {
					k++;
					for (boolean b : Exist[k])
						possible &= b;
				}
				k--;
			}

			public StringPermutation(String s) {
				CreateExist();
				int generalMax = (1 << Max) - 1;
				int[] masks = new int[Max + 1];
				for (int i = 1; i <= Max; i++) {
					masks[i] = (1 << i) - 1;
				}
				int current = 0;
				for (int i = 1; i <= s.length(); i++) {
					int value = (s.charAt(i - 1) == '1') ? 1 : 0;
					current = ((current << 1) | value) & generalMax;
					for (int j = 1, len = Math.min(i, Max); j <= len; j++) {
						Exist[j][current & masks[j]] = true;
					}
				}
				StartPart = s.substring(0, Math.min(s.length(), Max));
				EndPart = s.substring(Math.max(s.length() - Max, 0), s.length());
				UpdateMaxK();
			}

			private void UpdateExistWith(StringPermutation o1) {
				for (int i = 1; i <= Max; i++) {
					for (int j = 0, len = 1 << i; j < len; j++) {
						Exist[i][j] |= o1.Exist[i][j];
					}
				}
			}

			public StringPermutation(StringPermutation o1, StringPermutation o2) {
				this(o1.EndPart.concat(o2.StartPart));
				String s1 = o1.StartPart.concat(o2.StartPart);
				String s2 = o1.EndPart.concat(o2.EndPart);
				UpdateExistWith(o1);
				UpdateExistWith(o2);
				k = Math.max(o1.k, o2.k);
				StartPart = s1.substring(0, Math.min(s1.length(), Max));
				EndPart = s2.substring(Math.max(s2.length() - Max, 0), s2.length());
				UpdateMaxK();
			}
		}

		public void solve(int testNumber, InputReader in, PrintWriter out) {
			int n = in.NextInt();
			StringPermutation[] s = new StringPermutation[n];
			for (int i = 0; i < n; i++) {
				s[i] = new StringPermutation(in.next());
			}
			int m = in.NextInt();
			{
				StringPermutation[] ss = new StringPermutation[m + n];
				for (int i = 0; i < n; i++) {
					ss[i] = s[i];
				}
				s = ss;
			}
			for (int i = 0; i < m; i++) {
				int u = in.NextInt() - 1;
				int v = in.NextInt() - 1;
				s[n + i] = new StringPermutation(s[u], s[v]);
				out.println(s[n + i].k);
			}
		}

	}

	public static int GetMax(int[] ar) {
		int max = Integer.MIN_VALUE;
		for (int a : ar) {
			max = Math.max(max, a);
		}
		return max;
	}

	public static int[] GetCount(int[] ar) {
		return GetCount(ar, GetMax(ar));
	}

	public static int[] GetCount(int[] ar, int maxValue) {
		int[] dp = new int[maxValue + 1];
		for (int a : ar) {
			dp[a]++;
		}
		return dp;
	}

	static class InputReader {
		public BufferedReader reader;
		public StringTokenizer tokenizer;

		public InputReader(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream), 32768);
			tokenizer = null;
		}

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

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

		public long NextLong() {
			return Long.parseLong(next());
		}

		public double NextDouble() {
			return Double.parseDouble(next());
		}

		public int[] NextIntArray(int n) {
			return NextIntArray(n, 0);
		}

		public int[] NextIntArray(int n, int offset) {
			int[] a = new int[n];
			for (int i = 0; i < n; i++) {
				a[i] = NextInt() - offset;
			}
			return a;
		}

		public int[][] NextIntMatrix(int n, int m) {
			return NextIntMatrix(n, m, 0);
		}

		public int[][] NextIntMatrix(int n, int m, int offset) {
			int[][] a = new int[n][m];
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					a[i][j] = NextInt() - offset;
				}
			}
			return a;
		}
	}
}