The secret server of ICPC (Inter-Continental Programming Company) uses two passwords, v and w. v and w have the property that v|w| = w|v| . That is, if you concatenate v |w| times and w |v| times, they are the same (|v| denotes the length of string v). For example if v = ab and w = abab, we get v4 = w2 = abababab. The trivial case where v = w is not allowed, as it is not secure. As it is not easy to memorize the two strings, the system administrator has hidden them into a set of n strings: there are two distinct strings x and y in the set of n strings such that v is a prefix of x and (x = vv′) and w is a suffix of y (y = w′w).
Given the set of strings, write a program which helps finding the password pair
Your program is to read from standard input. The input consists of T test cases. The number of test cases T is given in the first line of the input. Each test case starts with an integer n, the number of strings in the set, where 2 ≤ n ≤ 200. Each of the following n lines contains one string in English lower case whose length is equal to or smaller than 20,000.
Your program is to write to standard output. Print exactly one line for each test case. Each line should contain two integer values |v| and |w| where v|w| = w|v| for some strings x and y in the set such that v is a prefix of x and w is a suffix of y. Also, |v| < |w|. If there are two or more such pairs, print the one where |v| + |w| is the greatest. The uniqueness of such password pair is guaranteed if it exists. If there is no such pair, print ‘0 0’.
2 3 abcabe defg bcabab 3 abcdef ghijkl mnopqr
2 4 0 0