Description

For an integer set, we define an "addition equation" as follows: some element of the set can be expressed as the sum of other elements in the set. For example, in the set ${1,2,3}$, there is one addition equation: $3=1+2$. Moreover, $3=1+2$ and $3=2+1$ are the same addition equation, and it is the only addition equation of this set. Given an integer set, write a program to find the number of its addition equations.

Input Format

The first line contains $t$, indicating the number of test cases.

The next $t$ lines each describe one test case. Each line starts with an integer $m$, the number of elements in the set, followed by $m$ distinct integers $x_i$, which are the elements of the set.

Output Format

For each test case, output one integer, the number of addition equations in the set.

3
3 1 2 3
3 1 2 5
6 1 2 3 5 4 6

1
0
7

Hint

$1\le t\le 10$，$1\le m \le 30$，$1\le x\le 1000$。

Translated by ChatGPT 5