题目描述

本题中，我们用 $s_i$ 表示第 $i$ 个字符串。

初始时给你 $n(1 \le n \le 100)$ 个 01 字符串 $s_1, s_2, \ldots, s_n$。这 $n$ 个字符串均由字符 '0' 和 '1' 构成且它们的长度之和不超过 $100$。

然后你需要构造 $m$ 个新的字符串，这 $m$ 个字符串根据如下规则生成。

第 $m+i$ 个字符串（即 $s_{m+i}$）由第 $a_i$ 个字符串和第 $b_i$ 个字符串拼接而成。即 $s_{m+i} = s_{a_i} + s_{b_i}$（这里的 $+$ 表示字符串拼接操作）。

对于你生成的每个字符串，你需要找到并输出一个最大的整数 $k$，满足：

所有长度为 $k$ 的 01 字符串都是这个字符串的子串。

这里：

• 所有长度为 $1$ 的 01 字符串是：0、1
• 所有长度为 $2$ 的 01 字符串是：00、01、10、11
• 所有长度为 $3$ 的 01 字符串是：000、001、010、011、100、101、110、111
• 依次类推……

输入格式

第一行，一个整数 $n(1 \le n \le 100)$。

接下来 $n$ 行，每行包含一个 01 字符串，依次表示 $s_1, s_2, \ldots, s_n$。它们的总长度不超过 $100$。

接下来一行，包含一个整数 $m(1 \le m \le 100)$。

接下来 $m$ 行，每行包含两个整数 $a_i$ 和 $b_i$（$1 \le a_i, b_i \le n+i-1$），表示第 $m+i$ 个字符串由第 $a_i$ 和第 $b_i$ 个字符串构成（即 $s_{m+i} = s_{a_i} + s_{b_i}$）。

输出格式

输出共 $m$ 行，每行包含一个整数。

其中第 $i$ 行的整数表示 $s_{m+i}$ 对应的最大的 $k$（即所有长度为 $k$ 的 01 字符串都是 $s_{m+i}$ 的子串）。

5
01
10
101
11111
0
3
1 2
6 5
4 4

1
2
0

说明/提示

样例解释

$s_6 = \mathtt{0110}$，它的子串包含所有长度为 $1$ 的 01 串，但是不包含所有长度为 $2$ 的 01 串（比如 00），所以输出 $k = 1$.

$s_7 = \mathtt{01100}$，它的字符串包含所有长度为 $2$ 的 01 串，但是不包含所有长度为 $3$ 的 01 串（比如 000），所以输出 $k = 2$.

$s_8 = \mathtt{1111111111}$，他不包含长度为 $1$ 的子串 0，所以对应的 $k = 0$（$k = 0$ 表示空串，空串是所有字符串的子串）.

数据规模与约定

• 对于 $20\%$ 的数据，$n \le 2, m \le 5$，前 $n$ 个字符串长度之和不超过 $10$；
• 对于 $50\%$ 的数据，$n \le 10, m \le 10$，前 $n$ 个字符串长度之和不超过 $100$；
• 对于 $100\%$ 的数据，$1 \le n, m \le 100$，前 $n$ 个字符串长度之和不超过 $100$.