# Codeforces868d huge strings

Posted by yjjr's blog on February 6, 2018

You are given n stringss1, s2, ..., sn consisting of characters 0 and 1.m operations areperformed, on each of them you concatenate two existing strings into a new one.On thei-th operation the concatenationsaisbiis saved into a new stringsn +i(the operations are numbered starting from 1). After each operation you need tofind the maximum positive integerk such that all possible stringsconsisting of 0 and 1 of lengthk (there are 2k suchstrings) are substrings of the new string. If there is no suchk, print 0.

Input

The first line contains single integern(1 ≤ n ≤ 100) — thenumber of strings. The nextn lines contain stringss1, s2, ..., sn (1 ≤ |si| ≤ 100), one per line. The total length of strings is not greater than 100.

The next line contains single integerm(1 ≤ m ≤ 100) — thenumber of operations.m lines follow, each of them contains two integersai abdbi (1 ≤ ai, bi ≤ n + i - 1) — the number of strings that areconcatenated to formsn +i.

Output

Print m lines, each should containone integer — the answer to the question after the correspondingoperation.

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. Fork = 1 the two possiblebinary strings of lengthk are "0" and "1", they aresubstrings of the new string. Fork = 2 and greater there exist strings of lengthk that do notappear in this string (fork = 2 such string is "00"). So the answer is 1.

On the second operation the string "01100"is created. Now all strings of lengthk = 2 are present.

On the third operation the string "1111111111"is created. There is no zero, so the answer is 0.

Code

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define mem(x,num) memset(x,num,sizeof x)
using namespace std;
const int maxn=206;
int ans[maxn],n,m,l,r;
string s[maxn];

int work(int x){
rep(i,1,10)
rep(j,0,(1<<i)-1){
string t;
rep(k,0,i-1){
if(j&(1<<k))t+='1';
else t+='0';
}
if(s[x].find(t)==-1)return i-1;
}
}
int main()
{
scanf("%d",&n);
rep(i,1,n)cin>>s[i];
scanf("%d",&m);
rep(i,1,m){
scanf("%d%d",&l,&r);
s[n+i]=s[l]+s[r];
if(s[n+i].length()>1000)s[n+i]=s[n+i].substr(0,500)+s[n+i].substr(s[n+i].length()-500,500);
ans[n+i]=max(max(ans[l],ans[r]),work(n+i));
cout<<ans[n+i]<<endl;
}
return 0;
} 