18696번 - Crazy LCP 다국어

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

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.