|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|2 초||512 MB||8||1||1||12.500%|
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 4 aab abc aac xba 3 2 3 1 3 3 4
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.