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

public class Main {
	public static void main(String args[]) {new Main().run();}

	FastReader in = new FastReader();
	PrintWriter out = new PrintWriter(System.out);
	void run(){
		work();
		out.flush();
	}
	long mod=1000000007;
	long gcd(long a,long b) {
		return a==0?b:b>=a?gcd(b%a,a):gcd(b,a);
	}
	void work() {
		int[][][] A=new int[200][11][];
		int[][] count=new int[200][11];
		String[] strs=new String[200];
		int n=in.nextInt();
		int i=0;
		for(;i<n;i++) {
			String str=in.next();
			for(int j=1;j<=10;j++) {
				A[i][j]=new int[1<<j];
				for(int k=0;k+j<=str.length();k++) {
					int v=get(str.substring(k,k+j));
					if(A[i][j][v]==0) {
						A[i][j][v]=1;
						count[i][j]++;
					}
				}
			}
			if(str.length()>=20) {
				str=str.substring(0,10)+str.substring(str.length()-10);
			}
			strs[i]=str;
		}
		int m=in.nextInt();
		out:
		for(;i<n+m;i++) {
			int a=in.nextInt()-1,b=in.nextInt()-1;
			String str=strs[a]+strs[b];
			for(int j=1;j<=10;j++) {
				A[i][j]=new int[1<<j];
				for(int k=0;k<1<<j;k++) {
					A[i][j][k]=A[a][j][k]|A[b][j][k];
					count[i][j]+=A[i][j][k];
				}
				for(int k=1;k<j;k++) {
					int l=j-k;
					if(k>strs[a].length()||l>strs[b].length())continue;
					int v=get(strs[a].substring(strs[a].length()-k)+strs[b].substring(0,l));
					if(A[i][j][v]==0) {
						A[i][j][v]=1;
						count[i][j]++;
					}
				}
			}
			if(str.length()>=20) {
				str=str.substring(0,10)+str.substring(str.length()-10);
			}
			strs[i]=str;
			for(int j=10;j>0;j--) {
				if(count[i][j]==1<<j) {
					out.println(j);
					continue out;
				}
			}
			out.println(0);
		}
	}
	private int get(String s) {
		int cur=0;
		for(int i=0;i<s.length();i++) {
			cur=(cur<<1)+s.charAt(i)-'0';
		}
		return cur;
	}
}	



class FastReader
{
	BufferedReader br;
	StringTokenizer st;

	public FastReader()
	{
		br=new BufferedReader(new InputStreamReader(System.in));
	}


	public String next() 
	{
		while(st==null || !st.hasMoreElements())//回车，空行情况
		{
			try {
				st = new StringTokenizer(br.readLine());
			} catch (IOException e) {
				e.printStackTrace();
			}
		}
		return st.nextToken();
	}

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

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