Server Time: Sun Dec 16, 2018 8:24 pm
Welcome ( logout
1073 - DNA Sequence
  PDF (English) Statistics Forum
Time Limit: 4 second(s) Memory Limit: 32 MB

You are given a list of strings over the alphabet A (for adenine), C (cytosine), G (guanine), and T (thymine), and your task is to find the shortest string (which is typically not listed) that contains all given strings as substrings. If there are several such strings of shortest length, find the smallest in alphabetical/lexicographical order.

Input

Input starts with an integer T (≤ 35), denoting the number of test cases.

Each case starts with an integer denoting the number of strings n (1 ≤ n ≤ 15) in a single line. Then these n strings (1 ≤ length ≤ 100) follow, one on each line, and they consist of the letters 'A', 'C', 'G' and 'T' only.

Output

For each case, print the case number and the shortest (and lexicographically smallest) string according to the description above.

Sample Input

Output for Sample Input

2

2

TGCACA

CAT

3

TAC

ACT

CTA

Case 1: TGCACAT

Case 2: ACTAC

 


Special Thanks: Jane Alam Jan (Description, Solution, Dataset)
Developed and Maintained by
JANE ALAM JAN
Copyright © 2012
LightOJ, Jane Alam Jan