21818번 - Do You Know Your ABCs? 다국어

문제

Farmer John's cows have been holding a daily online gathering on the "mooZ" video meeting platform. For fun, they have invented a simple number game to play during the meeting to keep themselves entertained.

Elsie has three positive integers $A,ドル $B,ドル and $C$ (1ドル\le A\le B\le C$). These integers are supposed to be secret, so she will not directly reveal them to her sister Bessie. Instead, 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$), claiming 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; the integers $x_i$ might not correspond to any valid triple $(A,B,C)$.

This is too hard for Bessie to wrap her head around, so it is up to you to determine the number of triples $(A,B,C)$ that are consistent with the numbers Elsie presented (possibly zero).

Each input file will contain $T$ (1ドル\le T\le 100$) test cases that should be solved independently.

입력

The first input line contains $T$.

Each test case starts with $N,ドル the number of integers Elsie gives to Bessie.

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

출력

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

제한

힌트

For $x=\{4,5,7,9\},ドル the five possible triples are as follows: $$(2, 2, 5), (2, 3, 4), (2, 4, 5), (3, 4, 5), (4, 5, 7).$$