Problem: 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.

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.*;
 
public class Main{
	static BufferedReader br = 
            new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = 
            new BufferedWriter(new OutputStreamWriter(System.out));
    static StringTokenizer st;
	
    public static void main(String args[]) throws IOException{
        Scanner sc = new Scanner(System.in);
        String str;
        String[] B = new String[200];
        String[] F = new String[200];
        boolean[][][] A = new boolean[200][10][1 << 10];
        int n, m, l, i, j, k, ii, a, b, s, f;
        n = getInt();
        for(i = 0; i < n; i++) {
        	str = getStr2();
        	l = str.length();
        	for(j = 0; j < 10; j++) {
        		for(k = 0; k < l-j; k++) {
        			s = 0;
        			for(ii = k; ii <= k+j; ii++) s += (str.charAt(ii) - '0')*(1 << (ii-k));
        			A[i][j][s] = true;
        		}
        	}
        	B[i] = str.substring(Math.max(l-10, 0), l);
        	F[i] = str.substring(0, Math.min(l, 10));
        }
        m = getInt();
        for(i = n; i < n+m; i++) {
        	a = getInt()-1;
        	b = getInt()-1;
        	if(F[a].length() < 10) F[i] = (F[a] + F[b]).substring(0, Math.min(F[a].length() + F[b].length(), 10));
        	else F[i] = F[a];
        	if(B[b].length() < 10) B[i] = (B[a] + B[b]).substring(Math.max(B[a].length() + B[b].length()-10, 0), B[a].length() + B[b].length());
        	else B[i] = B[b];
        	str = B[a].concat(F[b]);
        	l = str.length();
        	for(j = 0; j < 10; j++) {
        		for(k = 0; k < (1 << (j+1)); k++) {
        			if(A[a][j][k] || A[b][j][k]) {
        				A[i][j][k] = true;
        			}
        		}
        		for(k = 0; k < l-j; k++) {
        			s = 0;
        			for(ii = k; ii <= k+j; ii++) s += (str.charAt(ii) - '0')*(1 << (ii-k));
        			A[i][j][s] = true;
        		}
    		}
        	for(j = 9; j >= 0; j--) {
        		f = 1;
        		for(k = 0; k < (1 << (j+1)); k++) {
        			if(!A[i][j][k]) {
        				f = 0;
        				break;
        			}
        		}
        		if(f == 1) break;
        	}
        	bw.write((j+1)+"\n");
        }
        bw.close();
    }
    
    static void getToken() throws IOException{
    	if(st != null && st.hasMoreTokens()) return;
    	st = new StringTokenizer(br.readLine());
    }

    static String getStr2() throws IOException{
    	getToken();
    	return st.nextToken();
    }
    
    static int getInt() throws IOException{
    	getToken();
    	return Integer.parseInt(st.nextToken());
    }
    
}