Description

Farmer John’s cows are holding their daily meeting on the mooZ video conferencing platform. They have invented a simple number game to make the meeting more fun.

Elsie has three positive integers $A$, $B$, and $C$ ($1\le A\le B\le C$). These numbers are secret, and she will not tell them directly to her sister Bessie. She tells Bessie $N$ ($4\le N\le 7$) distinct integers $x_1,x_2,\ldots,x_N$ ($1\le x_i\le 10^9$), and claims that each $x_i$ is one of $A$, $B$, $C$, $A+B$, $B+C$, $C+A$, or $A+B+C$. However, Elsie may be lying; these integers $x_i$ might not correspond to any valid $(A,B,C)$.

Bessie cannot figure it out, so you need to compute the number of triples $(A,B,C)$ that are consistent with the numbers Elsie provided.

Each input contains $T$ ($1\le T\le 100$) test cases that must be solved independently.

Input Format

The first line of input contains $T$.

For each test case, the first line contains $N$, the number of integers Elsie gave to Bessie.

The second line of each test case contains $N$ distinct integers $x_1,x_2,\ldots,x_N$.

Output Format

For each test case, output the number of triples $(A,B,C)$ that are consistent with the numbers Elsie provided.

10
7
1 2 3 4 5 6 7
4
4 5 7 8
4
4 5 7 9
4
4 5 7 10
4
4 5 7 11
4
4 5 7 12
4
4 5 7 13
4
4 5 7 14
4
4 5 7 15
4
4 5 7 16

1
3
5
1
4
3
0
0
0
1

Hint

Sample Explanation

For $x=\{4,5,7,9\}$, the five possible triples are:

$$(2, 2, 5), (2, 3, 4), (2, 4, 5), (3, 4, 5), (4, 5, 7).$$

Test Point Properties

• In test points $1 \sim 4$, all $x_i$ are at most $50$.
• Test points $5 \sim 5$ satisfy $N=7$.
• Test points $7 \sim 15$ have no additional constraints.

Notes

Problem author: Benjamin Qi.

Translated by ChatGPT 5