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 $AA$, $BB$, and $CC$ ($1\le A\le B\le C1\backslash le\; A\backslash le\; B\backslash le\; C$). These integers are supposed to be secret, so she will not directly reveal them to her sister Bessie. Instead, she tells Bessie $NN$ ($4\le N\le 74\backslash le\; N\backslash le\; 7$) distinct integers $x_1,x_2,\dots ,x_{N}x\_1,x\_2,\backslash ldots,x\_N$ ($1\le x_i\le {10}^{9}1\backslash le\; x\_i\backslash le\; 10^9$), claiming that each $x_{i}x\_i$ is one of $AA$, $BB$, $CC$, $A+BA+B$, $B+CB+C$, $C+AC+A$, or $A+B+CA+B+C$. However, Elsie may be lying; the integers $x_{i}x\_i$ might not correspond to any valid triple $(A,B,C)(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)(A,B,C)$ that are consistent with the numbers Elsie presented (possibly zero).

Each input file will contain $TT$ ($1\le T\le 1001\backslash le\; T\backslash le\; 100$) test cases that should be solved independently.

입력

The first input line contains $TT$.

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

The second line of each test case contains $NN$ distinct integers $x_1,x_2,\dots ,x_{N}x\_1,x\_2,\backslash ldots,x\_N$.

출력

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

힌트

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

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