MAIN72 - Subset sum

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

Added by:Mahesh Chandra Sharma
Date:2011-03-13
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own problem used for NSIT-IIITA main contest #7

hide comments
2017-06-21 11:02:41
dp + unordered set ...!!!
AC in 1 go
2017-03-06 15:27:52 shahzada
Nice dp.
2016-12-29 18:00:39
printf-scanf AC 0.01
cin-cout AC 0.02
ios::sync_with_stdio(false) AC 0.01

Last edit: 2016-12-29 18:01:20
2016-12-06 08:21:39
tighter constraints.. so use InputReader in case of java..
2016-10-21 19:41:39
whop one more dp.
2016-10-05 17:23:48 Autorun
TLE with python 3, even with some optimizations in I/O.
2016-06-28 22:41:35 Amola Singh
Finally 50th! Nice problem.
2016-06-27 10:05:51
can be solved even without dp
2016-06-17 21:00:55
After this try BADXOR of spoj !!
2015-12-26 10:59:31 sneh sajal
good Dp :)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.