MooZ Video Conference Cow Game

Farmer John’s cows are holding their daily gathering on the MooZ video conferencing platform. In order to add some fun, Elsie invented a simple number game. She secretly chooses three positive integers $A$, $B$, and $C$ (with $1\le A\le B\le C$) and then tells her sister Bessie $N$ distinct numbers $x_1,x_2,\ldots,x_N$ ($4\le N\le 7$) such that each $x_i$ is claimed to be one of the seven values [ {A,; B,; C,; A+B,; B+C,; A+C,; A+B+C
] However, Elsie might be lying so that the given set of numbers does not correspond to any valid triple $(A,B,C)$. Bessie needs your help to count the number of ordered triples $(A,B,C)$ that could possibly produce a superset (with respect to set inclusion) of the given numbers. Each test case is independent.

Input Format: The input begins with an integer $T$ ($1\le T\le 100$). Each test case starts with an integer $N$, followed by a line containing $N$ distinct integers $x_1,x_2,\ldots,x_N$ ($1\le x_i\le 10^9$). It is guaranteed that $N$ is between 4 and 7 inclusive.

Output Format: For each test case output a single integer -- the number of triples $(A,B,C)$ with $1\le A\le B\le C$ such that every provided number $x_i$ belongs to the set $\{A,B,C,A+B,A+C,B+C,A+B+C\}$.

Note: In the expressions above, $A+B+C$ is always the largest number and $A$ is always the smallest number among the seven values.

inputFormat

The first line contains an integer T, the number of test cases. For each test case:

• The first line contains an integer N (with 4 ≤ N ≤ 7).
• The second line contains N distinct integers x1 x2 ... xN (each between 1 and 109).

outputFormat

For each test case, output a single line containing one integer -- the count of valid triples (A,B,C) that can produce a superset of the given numbers.

sample

3
7
1 3 4 6 7 9 10
4
8 4 3 1
6
10 8 7 5 3 2

1
1
1