Twins Birthday

All submissions for this problem are available.
Alice and Eve are twins. On their birthday they got total of N toys. Each toy i have a certain cost v_{i}. Alice likes expensive toys while Eve doesn't care about expensive toys as long as she gets a lot of toys. Their Parents want to divide these N toys between Alice and Eve. They want to be fair to each of them while distributing toys. So they devise the following strategy:
 The total value of all toys of Alice should be equal to total value of all toys of Eve.
 Each toy of Alice should be more expansive than the toys of Eve i.e. the least expansive toy of Alice should have cost greater than or equal to cost of the most expensive toy of Eve.
 There can be toys which are neither given to Alice nor Eve.
 Alice and Eve should get atleast one toy each.
Find the total numbers of ways in which their parents can divide the toys between them by following the above policy.
Also note that cost of two or more toys can be same and these toys will be considered differently.
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows:
 The first line of each test will contain a single integer N, total number of toys.
 The second line of each test case will contain N space separated integers, which represent the cost of N toys.
Output
 For each test case, output a single line containing a single integer which is the total number of in which toys can be distributed.
Constraints
 1 ≤ T ≤ 20
 2 ≤ N ≤ 30
 1 ≤ v_{i} ≤ 1000
Example
Input: 1 5 1 2 3 4 5 Output: 4
Explanation
Example case 1.
Eve Alice
1,2 3
1,3 4
1,4 5
2,3 5
So total of 4 ways.
Author:  prashant89 
Tags  prashant89 
Date Added:  28022014 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, JAR, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions