在这个问题中，给定一个包含 $N$ 个字符串的数组，这些字符串的索引从 $1$ 到 $N$（顺序与输入中给出的顺序相同）。接着给定 $Q$ 个查询，每个查询包含两个整数 $L$ 和 $R$，你需要回答在索引范围 $[L, R]$（包含 $L$ 和 $R$）内，哪两个字符串的最长公共前缀（LCP）长度最大。

输入格式

程序将在一个或多个测试用例上进行测试。输入的第一行是一个整数 $T$ ($1 \le T \le 100$)，表示测试用例的数量。

每个测试用例的第一行包含一个整数 $N$ ($2 \le N \le 10^5$)，表示字符串的数量，随后一行包含 $N$ 个由空格分隔的非空小写英文字母字符串。每个测试用例中字符串的总长度不超过 $200,000$。

接下来的一行包含一个整数 $Q$ ($1 \le Q \le 10^5$)，表示查询的数量，随后有 $Q$ 行，每行包含两个由空格分隔的整数 $L$ 和 $R$，表示上述查询 ($1 \le L < R \le N$)。

输出格式

对于每个查询，输出一行，包含一个整数，表示上述最长公共前缀的最大长度。

样例

输入格式 1

1
4
aab abc aac xba
3
2 3
1 3
3 4

输出格式 1

1
2
0

说明

字符串 $S$ 的前缀是指从 $S$ 的左侧开始的 $0$ 个或多个字符，两个字符串之间的公共前缀是指同时为这两个字符串前缀的字符串。