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.*;
import java.util.*;

public class Main {
	static BufferedReader reader = null;
	static StringTokenizer tokenizer = null;
	static PrintWriter writer = null;

	static String nextToken() throws IOException {
		while (tokenizer == null || !tokenizer.hasMoreTokens()) {
			tokenizer = new StringTokenizer(reader.readLine());
		}
		return tokenizer.nextToken();
	}

	static int nextInt() throws NumberFormatException, IOException {
		return Integer.parseInt(nextToken());
	}

	static double nextDouble() throws NumberFormatException, IOException {
		return Double.parseDouble(nextToken());
	}

	static long nextLong() throws NumberFormatException, IOException {
		return Long.parseLong(nextToken());
	}

	static class State {
		String l;
		String r;
		int k;

		ArrayList<HashSet<Long>> done;

		public State(int mx) {
			done = new ArrayList<>();
			for (int i = 0; i <= mx; i++) {
				done.add(new HashSet<>());
			}
		}
	}

	public static void main(String[] args) throws IOException {
		reader = new BufferedReader(new InputStreamReader(System.in));
		writer = new PrintWriter(System.out);
		banana();
		reader.close();
		writer.close();
	}

	static int MX = 60;

	static State process(String s, int donek) {
		State state = new State(MX);
		state.k = donek;

		for (int k = state.k + 1; k <= MX; k++) {
			HashSet<Long> sk = state.done.get(k);
			for (int i = 0; i < s.length(); i++) {
				if (i + k <= s.length()) {
					long value = Long.parseLong(s.substring(i, i + k), 2);
					sk.add(value);
				}
			}
			if (sk.size() == (1L << k)) {
				state.k = k;
			}
		}

		int limit = MX;
		if (s.length() <= limit) {
			state.l = s;
			state.r = s;
		} else {
			state.l = s.substring(0, limit);
			state.r = s.substring(s.length() - limit);
		}
		return state;
	}

	static State mergeStates(State s1, State s2) {
		State midState = process(s1.r + s2.l, Math.max(s1.k, s2.k));

		for (int k = midState.k + 1; k <= MX; k++) {
			HashSet<Long> mk = midState.done.get(k);
			mk.addAll(s1.done.get(k));
			mk.addAll(s2.done.get(k));
			if (mk.size() == (1L << k)) {
				midState.k = k;
			}
		}

		if (s1.l.length() == MX) {
			midState.l = s1.l;
		} else {
			midState.l = s1.l + s2.l;
			if (midState.l.length() > MX) {
				midState.l = midState.l.substring(0, MX);
			}
		}

		if (s2.r.length() == MX) {
			midState.r = s2.r;
		} else {
			midState.r = s1.r + s2.l;
			if (midState.r.length() > MX) {
				midState.r = midState.r.substring(midState.r.length() - MX);
			}
		}

		return midState;
	}

	static void banana() throws NumberFormatException, IOException {
		int n = nextInt();
		ArrayList<State> al = new ArrayList<>();
		for (int i = 0; i < n; i++) {
			al.add(process(nextToken(), 0));
		}
		int m = nextInt();
		for (int j = 0; j < m; j++) {
			int a = nextInt();
			int b = nextInt();
			a--;
			b--;
			State res = mergeStates(al.get(a), al.get(b));
			writer.println(res.k);
			al.add(res);
		}
	}
}