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.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class D438 {
	public static void main(String[] args) {
		FS scan = new FS(System.in);
		PrintWriter out = new PrintWriter(System.out);
		int N =  scan.nextInt();
		int MAX = 8;
		int LEN = 500;
		StringBuilder[] s = new StringBuilder[200], e = new StringBuilder[200];
		boolean[][] sol = new boolean[200][1<<(MAX+1)];
		
		for(int i=0;i<N;i++){
			s[i] = e[i] = new StringBuilder(scan.next());
			for(int j=0;j<=s[i].length();j++){
				int bit = 1;
				int l = Math.min(MAX, s[i].length()-j);
				for(int k=0;k<l;k++){
					if(s[i].charAt(j+k)=='1')bit = (bit<<1)+1;
					else bit <<=1;
					sol[i][bit] = true;
				}
			}
		}
		int Q = scan.nextInt();
		for(int i=0;i<Q;i++){
			int a = scan.nextInt()-1, b = scan.nextInt()-1;
			
			StringBuilder x = new StringBuilder(e[a]).append(s[b]);
			for(int j=0;j<(1<<MAX);j++){
				if(sol[a][j]||sol[b][j])sol[i+N][j] = true;
			}
			for(int j=0;j<=x.length();j++){
				int bit = 1;
				int l = Math.min(MAX, x.length()-j);
				for(int k=0;k<l;k++){
					if(x.charAt(j+k)=='1')bit = (bit<<1)+1;
					else bit <<=1;
					sol[i+N][bit] = true;
				}
			}
			s[N+i] = new StringBuilder(x.substring(0,Math.min(x.length(), LEN)));
			e[i+N] = new StringBuilder(x.substring(Math.max(0, x.length()-LEN)));
			if(x.length()>LEN){
				s[N+i] = s[a];
				e[N+i] = e[b];
			}
			for(int j=2;j<(1<<20);j<<=1){
				boolean cool = true;
				for(int k=0;k<j;k++){
					if(!sol[i+N][j+k]){
						cool = false;
						break;
					}
				}
				if(!cool){
					out.println(Integer.numberOfTrailingZeros(j)-1);
					break;
				}
			}
		}
		out.close();
	}
	public static int calc(StringBuilder s) {
		
		int lo = 1, hi = Math.min(s.length(), 20), sol = 0;
		while(lo<=hi) {
			int mid = lo+hi>>1;
			
			int x = 0;
			for(int i=0;i<mid;i++){
				if(s.charAt(i)=='1')x|=(1<<(mid-1));
			}
			
			boolean[] seen = new boolean[1<<mid];
			seen[x] = true;
			int count = (1<<mid)-1;
			for(int i=mid;i<s.length();i++){
				x>>=1;
				if(s.charAt(i)=='1')x|=(1<<(mid-1));
				if(!seen[x]){
					count--;
					seen[x] = true;
				}
				if(count==0)break;
			}
			if(count==0){
				sol = mid;
				lo = mid+1;
			}else{
				hi = mid-1;
			}
		}
		
		return sol;
		
	}
	public static boolean check(int m, int K) {
		boolean[] count = new boolean[(1<<K)];
		int mask = (1<<K)-1;
		while(m>=(1<<K)){
			int temp = m&mask;
			count[temp] = true;
			m>>=1;
		}
		boolean found = true;
		for(boolean z : count)found&=z;
		return found;
	}
	
	private static class FS {
		BufferedReader br;
		StringTokenizer st;
		public FS(InputStream in) {
			br = new BufferedReader(new InputStreamReader(in));
		}
		String next(){
			while(st==null||!st.hasMoreElements()){
				try{st = new StringTokenizer(br.readLine());}
				catch(IOException e){e.printStackTrace();}
			}
			return st.nextToken();
		}
		int nextInt() {return Integer.parseInt(next());}
		long nextLong() {return Long.parseLong(next());}
		double nextDouble() { return Double.parseDouble(next());}
	}
}