DA-S95-CA1

Time Limit: 1 Second    Memory Limit: 3072 KB

You can find the related question in the Homework 1.

Input

In the first line, there will be given an anonymous integer k ( k<=50) which is the number of test cases. In the next following 2*k lines, for each test case there will be 2 lines with the same format given in the Homework1.

Output

You should print one integer per line which is the answer to the corresponding test case.

Sample Input

2
7 2 4
2 2 2 2 1 1 1
2 7 1
10 7

Sample Output

2
12
Submit