No tag edit access

D. Huge Strings

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou are given *n* strings *s*_{1}, *s*_{2}, ..., *s*_{n} 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*_{ai}*s*_{bi} is saved into a new string *s*_{n + 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 2^{k} 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 *s*_{1}, *s*_{2}, ..., *s*_{n} (1 ≤ |*s*_{i}| ≤ 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*_{i} abd *b*_{i} (1 ≤ *a*_{i}, *b*_{i} ≤ *n* + *i* - 1) — the number of strings that are concatenated to form *s*_{n + 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.

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/15/2019 03:48:59 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|