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
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

n = int(input())
l = 12
pow2 = [1]
for _ in range(l + 5):
    pow2.append(2 * pow2[-1])
s = [list(input().rstrip()) for _ in range(n)]
x = [0]
for i in pow2[1:]:
    x.append(x[-1] + i)
dp = [[0] * pow2[l + 1] for _ in range(n)]
for i in range(n):
    si, dpi = s[i], dp[i]
    for j in range(len(si)):
        u = 0
        for k in range(min(l, len(si) - j)):
            if si[j + k] & 1:
                u ^= pow2[k]
            dpi[u + x[k]] = 1
m = int(input())
ans = []
for _ in range(m):
    a, b = map(int, input().split())
    sa, sb = s[a - 1], s[b - 1]
    dpa, dpb = dp[a - 1], dp[b - 1]
    s0 = sa + sb
    dp0 = [i | j for i, j in zip(dpa, dpb)]
    for j in range(len(s0)):
        u = 0
        for k in range(min(l, len(s0) - j)):
            if s0[j + k] & 1:
                u ^= pow2[k]
            dp0[u + x[k]] = 1
    if len(s0) > 2 * l + 10:
        l0 = l + 5
        s0 = s0[:l] + s0[-l:]
    s.append(s0)
    dp.append(dp0)
    ans0 = 0
    while True:
        ok = 1
        for i in range(x[ans0], x[ans0 + 1]):
            if not dp0[i]:
                ok = 0
                break
        if not ok:
            break
        ans0 += 1
    ans.append(ans0)
sys.stdout.write("\n".join(map(str, ans)))