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 ≤ 105) 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 ≤ 106. The line following the last string contains a single integer Q (1 ≤ Q ≤ 106), 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 2 5 daffodilpacm daffodiliupc distancevector distancefinder distinctsubsequence 4 12 15 34 45 2 acm icpc 2 12 22
2/2 Sample Output Case 1: 8 1 8 4 Case 2: 0 4