I don't have a good name for this one...

Ideas come to me naturally. Only two people in the entire history of mankind have ever said that with truth — Parsa and Leonhard.

Input

The first line contains a single integer $t (1 \leq t \leq 13)$ — the number of test cases. Each test case contains $n$ lines. The $i$-th line contains an integer $a_i (1 \leq a_i \leq 9)$. The sum of $n$ over all test cases doesn't exceed 65.

Output

For each test case, print one integer — the answer.

Constraints

$1 \le t \le 13$ $1 \leq a_i \leq 9$

Example 1

Input

3
2
3
1
2
3
4
5
6
7
9

5
28
9