You are given *n* strings *s*<sub class="lower-index">1</sub>, *s*<sub class="lower-index">2</sub>, ..., *s*<sub class="lower-index">*n*</sub> 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 *s*<sub class="lower-index">*a*<sub class="lower-index">*i*</sub></sub>*s*<sub class="lower-index">*b*<sub class="lower-index">*i*</sub></sub> is saved into a new string *s*<sub class="lower-index">*n* + *i*</sub> (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 2<sup class="upper-index">*k*</sup> such strings) are substrings of the new string. If there is no such *k*, print 0.
The first line contains single integer *n* (1 ≤ *n* ≤ 100) — the number of strings. The next *n* lines contain strings *s*<sub class="lower-index">1</sub>, *s*<sub class="lower-index">2</sub>, ..., *s*<sub class="lower-index">*n*</sub> (1 ≤ |*s*<sub class="lower-index">*i*</sub>| ≤ 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 *a*<sub class="lower-index">*i*</sub> abd *b*<sub class="lower-index">*i*</sub> (1 ≤ *a*<sub class="lower-index">*i*</sub>, *b*<sub class="lower-index">*i*</sub> ≤ *n* + *i* - 1) — the number of strings that are concatenated to form *s*<sub class="lower-index">*n* + *i*</sub>.
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.
5
01
10
101
11111
0
3
1 2
6 5
4 4
1
2
0
5
01
1
0011
0
01
6
5 5
3 2
4 2
6 7
5 1
9 7
1
1
1
2
1
2
5
111101000111100011100110000100
000111001
01101000
0000110100100010011001000000010100100111110110
0110001
10
5 5
2 2
5 6
1 1
1 7
10 6
6 2
11 1
3 6
8 2
2
2
2
3
3
4
3
4
2
3
1
1
1
1 1
0
5
110101010101010110000011011
111111
1000100011100111100101101010011111100000001001
00
1111101100001110000
10
4 3
6 6
7 5
8 8
8 7
10 8
11 9
10 12
13 13
12 13
4
4
4
4
4
4
4
4
4
4
5
100010010
0
1001100110010111
0001000011000111000011011000110000010010010001110001000011011
0100000100100
10
5 5
6 6
6 7
7 8
8 9
10 8
11 9
10 9
12 13
12 13
1
1
1
1
1
1
1
1
1
1
5
0
1
11
110000010001100101001
1101011011111
10
5 3
6 4
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 13
1
4
5
5
5
5
5
5
5
5
10
0
1
1111100000
0
1
0000
11000
1010001110010010110
01101001111
010101110110111111
20
10 3
11 4
12 5
13 6
14 7
15 8
16 9
17 16
18 17
19 18
20 19
21 20
22 21
23 22
24 23
25 24
26 25
27 26
28 27
29 28
2
2
3
3
3
4
5
6
6
6
6
6
6
6
6
6
6
6
6
6
10
0
1
1111
110000000
100000
1
1
000010100001110001
00100010110001101000111100100110010101001011
100110110011101
50
10 3
11 4
12 5
13 6
14 7
15 8
16 9
17 1
18 1
19 2
20 2
21 2
22 2
23 2
24 1
25 2
26 1
27 2
28 1
29 2
30 2
31 1
32 2
33 1
34 2
35 2
36 2
37 2
38 1
39 2
40 2
41 1
42 2
43 2
44 2
45 1
46 2
47 2
48 2
49 2
50 2
51 2
52 2
53 52
54 53
55 54
56 55
57 56
58 57
59 58
2
2
3
3
3
4
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
2
001010011100101110111
001100110011001100110011001100110011001100110011001100111001
14
1 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10
11 11
12 12
13 13
14 14
15 15
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
1
0
40
1 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10
11 11
12 12
13 13
14 14
15 15
16 16
17 17
18 18
19 19
20 20
21 21
22 22
23 23
24 24
25 25
26 26
27 27
28 28
29 29
30 30
31 31
32 32
33 33
34 34
35 35
36 36
37 37
38 38
39 39
40 40
41 41
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
011
100
63
1 1
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10
11 11
12 12
13 13
14 14
15 15
16 16
17 17
18 18
19 19
20 20
21 21
22 22
23 23
24 24
25 25
26 26
27 27
28 28
29 29
30 30
31 31
32 32
2 2
34 34
35 35
36 36
37 37
38 38
39 39
40 40
41 41
42 42
43 43
44 44
45 45
46 46
47 47
48 48
49 49
50 50
51 51
52 52
53 53
54 54
55 55
56 56
57 57
58 58
59 59
60 60
61 61
62 62
63 63
33 64
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
1
0000000000000000000000000000000000000000000000000000000000000000
25
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10
11 11
12 12
13 13
14 14
15 15
16 16
17 17
18 18
19 19
20 20
21 21
22 22
23 23
24 24
25 25
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
n = int(input())
data = []
for i in range(n):
	data.append(input())
m = int(input())
for q in range(m):
	u, v = map(int, input().split())
	tmp = data[u-1] + data[v-1]
	data.append(tmp)
	for k in range(1, 100):
		flag = True
		for j in range(0, 2**k):
			b = bin(j)[2:]
			b = "0"*(k-len(b)) + b
			if b not in tmp:
				flag = False
				break
		if not flag:
			print(k-1)
			break

