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