Anti-Rhyme Pairs

Input: Standard Input

Output: Standard Output

Often two words that rhyme also end in the same sequence of characters. We use this property to define the concept of an anti-rhyme. An anti-rhyme is a pair of words that have a similar beginning. The degree of anti-rhyme of a pair of words is further defined to be the length of the longest string S such that both strings start with S. Thus, “arboreal” and “arcturus” are an anti-rhyme pair of degree 2, while “chalkboard” and “overboard” are an anti-rhyme pair of degree 0.

You are given a list of words. Your task is, given a list of queries in the form (i, j), print the degree of anti-rhyme for the pair of strings formed by the i-th and the j-th words from the list.

Input

Input consists of a number of test cases. The first line of input contains the number of test cases T (T ≤ 35). Immediately following this line are T cases.

Each case starts with the number of strings N (1 ≤ N ≤ 10⁵) on a line by itself. The following N lines each contain a single non-empty string made up entirely of lower case English characters ('a' to 'z'), whose length L is guaranteed to be less than or equal to 10,000. In every case it is guaranteed that N*L ≤ 10⁶.

The line following the last string contains a single integer Q (1 ≤ Q ≤ 10⁶), the number of queries. Each of the Q lines following contain a query made up of two integers i and j separated by whitespace (1 ≤ i, j ≤ N).

Output

The output consists of T cases, each starting with a single line with “Case X:”, where X indicates the X-th case. There should be exactly Q lines after that for each case. Each of those Q lines should contain an integer that is the answer to the corresponding query in the input.

Sample Input Output for Sample Input

daffodilpacm

daffodiliupc

distancevector

distancefinder

distinctsubsequence

1 2

1 5

3 4

4 5

acm

icpc

1 2

2 2

Case 1:

Case 2:

Warning: I/O files is huge, make sure your I/O is fast.