시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 0 0 0 0.000%

문제

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.

입력

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 ≤ 100) representing the number of test cases. Followed by T test cases.

Each test case starts with a line containing an integer N (2 ≤ N ≤ 105) representing the number of strings followed by a line containing 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 ≤ 105) representing the number of queries followed by 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).

출력

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

예제 입력 1

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

예제 출력 1

1
2
0

힌트

A prefix of string S is the first (from the left) 0 or more characters from S, and a common prefix between 2 strings is a string which is a prefix in both of them.