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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.StringTokenizer;


public class D {

	static class Scanner{
		BufferedReader br=null;
		StringTokenizer tk=null;
		public Scanner(){
			br=new BufferedReader(new InputStreamReader(System.in));
		}
		public String next() throws IOException{
			while(tk==null || !tk.hasMoreTokens()) {
				String cad = br.readLine();
				if (cad == null)
					return null;
				tk=new StringTokenizer(cad);
			}
			return tk.nextToken();
		}
		public int nextInt() throws NumberFormatException, IOException{
			return Integer.valueOf(next());
		}
		public long nextLong() throws NumberFormatException, IOException{
			return Long.valueOf(next());
		}
		public double nextDouble() throws NumberFormatException, IOException{
			return Double.valueOf(next());
		}
	}
	
	
	
	static void aux(String a, HashSet<String>[] sets) {
		for(int tam = 1; tam < sets.length; tam++)
			for(int i = 0; i + tam <= a.length(); i++)
				sets[tam].add(a.substring(i, i + tam));
	}
	
	static class Cadena {
		HashSet<String>[] sets;
		int maxSet;
		String cad;
		@SuppressWarnings("unchecked")
		public Cadena(String a) {
			init(a);
		}
		void init(String a) {
			sets = new HashSet[10];
			for(int i = 1; i < sets.length; i++)
				sets[i] = new HashSet<String>();
			aux(a, sets);
			cad = a;	
		}
		public Cadena(String a, String b) {
			String tmp = a.substring(Math.max(0, a.length() - 9));
			tmp = tmp + b.substring(0, Math.min(9, b.length()));
			init(tmp);
			String nueva = a + b;
			if (nueva.length() > 20)
				nueva = nueva.substring(0, 10) + nueva.substring(nueva.length() - 10);
			cad = nueva;
		}

		Cadena join(Cadena o) {
			Cadena ret = new Cadena(cad, o.cad);
			for(int i = 1; i < sets.length; i++) {
				ret.sets[i].addAll(sets[i]);
				ret.sets[i].addAll(o.sets[i]);
			}
			int idx = 0;
			while(ret.sets[idx + 1].size() == (1<<(idx+1)) )
				idx++;
			System.out.println(idx);
			return ret;
		}
	}
	
	public static void main(String args[]) throws NumberFormatException, IOException {
		Scanner sc = new Scanner();
		int N = sc.nextInt();
		ArrayList<Cadena> cadenas = new ArrayList<Cadena>();
		for(int i = 0; i < N; i++)
			cadenas.add(new Cadena(sc.next()));
		int M = sc.nextInt();
		for(int i = 0; i < M; i++) {
			int a = sc.nextInt() - 1;
			int b = sc.nextInt() - 1;
			cadenas.add(cadenas.get(a).join(cadenas.get(b)));
		}
	}

}
