Crazy LCP

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 ≤ 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).

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