DNA Laboratory

Time limit1sMemory limit128 MB

Summary

Given up to 15 DNA strings, find the shortest string that contains all of them as substrings, breaking ties by lexicographic order.

Level: Hard8 of 10
Topics: Dynamic programming, Bit manipulation, String, Greedy
Solved: No attempts yet

Problem

An evil doctor has just started building his own DNA laboratory and is not yet up to date. He wants to extract his DNA, enhance it, and clone himself. He already knows how to extract DNA from his blood cells, but reading off a DNA sequence requires breaking the DNA into many short pieces and analyzing each piece separately. He has not figured out how to reassemble the pieces into the original sequence, so he has kidnapped a few clever students to solve the problem for him, and you are one of them.

You are given a list of strings over the alphabet A (adenine), C (cytosine), G (guanine), and T (thymine). Find the shortest string that contains every given string as a substring. If several such strings share that shortest length, output the lexicographically smallest one.

Input

The first line contains the number of scenarios.

Each scenario begins with a line containing the number of strings $n$ ( $1 \le n \le 15$ ). The next $n$ lines each contain one string. Every string has length between $1$ and $100$ and consists only of the characters A, C, G, and T.

Output

For each scenario, print a line Scenario #i:, where $i$ is the scenario number starting at $1$ . On the next line, print the shortest string that contains all of the scenario's strings as substrings; if several strings share that shortest length, print the lexicographically smallest one. Separate consecutive scenarios with a blank line.

Examples5

Example 1
Input
```
1
2
TGCACA
CAT
```
Expected output
```
Scenario #1:
TGCACAT
```
Example 2
Input
```
1
1
ACGTACGT
```
Expected output
```
Scenario #1:
ACGTACGT
```
Example 3
Input
```
1
3
ACGTAC
GTA
CGT
```
Expected output
```
Scenario #1:
ACGTAC
```
Example 4
Input
```
1
2
AT
TA
```
Expected output
```
Scenario #1:
ATA
```

Example 5

Input

2
2
TGCACA
CAT
2
AT
TA

Expected output

Scenario #1:
TGCACAT

Scenario #2:
ATA