Migrated from Lutece 920 Big Integers

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

To get big integers, we can concatenate small integers together, such as concatenate $32$ and $1$ to $321$, or concatenate $3$ and $21$ to $321$.

There is a set $S$ containing $N$ different integers. An integer $X$ is special if the following three conditions are satisfied:

1. Choose two nonempty subsets $A$ and $B$ from $S$, where $A$ and $B$ have no common elements.

2. There is at least one way to get $X$ by concatenating all numbers in $A$.

3. There is at least one way to get $X$ by concatenating all numbers in $B$.

Output the largest special integer $X$.

Input

A single integer $T$ in the first line, indicating the number of cases.

For each case:

There are multiple test cases.

A single integer $N$ is given in the first line.

$N$ different integers $a_1$, $a_2$, ..., $a_N$ are given in the second line.

$1\leq T \leq 50$

$2 \leq N \leq 6$;

$0 \leq a_i \leq 99$, $1 \leq i \leq N$;

There are no leading zeros.

CF：参加div.1的同学的最终得分 = 所有参加div.2同学$A$题的最高的$10$个得分的平均分 + 所有参加div.2同学$B$题的最高的$10$个得分的平均分 + 该同学div.1$A$题得分 $\times \frac{div.2 C题满分}{div.1 A题满分}$ + 该同学div.1$B$题得分 $\times \frac{div.2 D题满分}{div.1 B题满分}$ + 该同学div.1$C$题得分 $\times \frac{div.2 E题满分}{div.1 C题满分}$ + 该同学div.1$D$题得分$\times 3$ + 该同学div.1$E$题得分 $\times$ $5$

TC：参加div.1的同学的最终得分 =所有参加div.2同学$A$题的最高的$10$个得分的平均分 + 该同学div.1$A$题得分 $\times \frac{div.2 B题满分}{div.1 A题满分}$ +该同学div.1$B$题得分 $\times \frac{div.2 C题满分}{div.1 B题满分}$ + 该同学div.1$C$题得分 $\times$ $5$

Output

For each case, output "Case #i " first, $i$ is the case number, from $1$ to $T$. Then if you can get at least one special integer, output the largest one. Otherwise, output -1.

Samples

3
4
1 3 32 21
4
1 2 12 21
2
1 2

Case #1: 321
Case #2: 21
Case #3: -1

Resources

Sichuan State Programming Contest 2014