Statement

In this problem you are given an array of strings, these strings are given unique indexes from 1 to

*N*(in the same order as in the input). Then you are given

*Q*queries, each query consists of 2 integers

*L*and

*R*, to answer the query you need to find a pair of strings with different indexes in the range from

*L*to

*R*(inclusive), where the length of the longest common prefix for these 2 strings is the maximum among all other possible pairs.

Input

Your program will be tested on one or more test cases. The first line of the input will be a single integer

*T (1 ≤ T ≤ 20)*representing the number of test cases. Followed by

*T*test cases. Each test case starts with a line containing an integer

*N (2 ≤ N ≤ 10*representing the number of strings followed by a line containing

^{5})*N*non-empty strings of lower case English letters separated by a single space, representing the list of strings. The sum of lengths of the strings in each test case is not greater than 200,000.

Followed by a line containing an integer

*Q (1 ≤ Q ≤ 10*representing the number of queries followed by

^{5})*Q*lines, each line will contain 2 integers separated by a space,

*L R*, which represent a query as described above

*(1 ≤ L < R ≤ N)*.

Output

For each query print a single line containing an integer which is the maximum length of a longest common prefix as described above.

Example input

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

Example output

1 2 0

Time and memory limit:

- 5 seconds
- 256MB

**Problem source:** A2OJ