Longest Common Prefix

A prefix of a string S = a₁...a_n is defined as S' = a₁...a_m where m ≤ n. In other words, prefix of S is a continuous substring which starts from the beginning of S.

For example, let S = "CODER".

There are 5 prefixes of S, which are: "C", "CO", "COD", "CODE" and "CODER" itself.

Now, a common prefix of a collection of string U = {S₁, ..., S_N} is defined as a string which is a prefix for all strings in U.

For example, let U = { "MAU", "MAKAN", "MALAM" }.

There are 2 common prefixes of U, which are: "M" and "MA". Among these common prefixes, the longest common prefix is "MA" which has a length of 2.

In this task, you are given a collection of N strings and you have to determine what the longest common prefix of those N strings is.

Input

The first line of input contains an integer T (1 ≤ T ≤ 100) the number of cases. Each case begins with an integer N (2 ≤ N ≤ 5) denoting the number of strings in the collection. The next N lines each contains a string S_i. Each string consists of only uppercase alphabets ('A'..'Z') with length between 1 and 100.

Output

For each case, output in a line the "Case #X: Y" where X is the case number starts from 1, and Y is the longest common prefix of the given collection. You may assume the length of the longest common prefix is at least 1.

4
3
MAU
MAKAN
MALAM
2
CODER
CODING
2
ICPC
INDONESIA
3
ABCDEF
ABCD
ABCDEFGHIJ

Case #1: MA
Case #2: COD
Case #3: I
Case #4: ABCD