A. Gym Plates
time limit per test
1 second
memory limit per test
256 МБ
input
standard input
output
standard output

Yaman and Omar are playing in a gym, and they want to prepare themselves for the tournament.

The gym in which they exercise has $$$n$$$ barbell plates numbered from $$$1$$$ to $$$n$$$, and the weight of the $$$i$$$-th plate is $$$w_i$$$.

Yaman noticed that he can lift any number of barbell plates if the following condition is held:

  • For any digit from $$$0$$$ to $$$9$$$, the digit must not occur in the weights more than twice.

For example: Yaman can lift plates with weights $$$[11, 23, 2]$$$, but he can't lift $$$[10, 999]$$$ or $$$[99, 9, 10]$$$ because the digit $$$9$$$ repeated $$$3$$$ times.

Now Omar is wondering what is the maximum weight that Yaman can lift, help him to find it out.

Input

The first line contains the number of test cases $$$t$$$ $$$( 1 \le t \le 100 )$$$. A description of the test cases follows.

The first line of each test case contains one integer $$$n$$$ $$$( 1 \le n \le 100 )$$$ — the number of barbell plates in the gym

The second line contains $$$n$$$ integers $$$w_1, w_2, .., w_n$$$ $$$( 1 \le w_i \le 10^{16} )$$$ — the wights of the barbell plates

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$100$$$

Output

For each test case, output the maximum weight that Yaman can lift.

Example
Input
3
3
11 23 2
1
222
3
97 98 99
Output
36
0
195