You are given an array of N integers. Now you want to find the sum of all those integers which can be expressed as the sum of at least one subset of the given array.

Input

First line contains T the number of test case. then T test cases follow, first line of each test case contains N (1 <= N <= 100) the number of integers, next line contains N integers, each of them is between 0 and 1000 (inclusive).  

Output

For each test case print the answer in a new line.

Example

Input:
2
2
0 1
3
2 3 2

Output:
1
21