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,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$ distinct integers $x_1,x_2,..,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,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).

Input

The first line contains the number of test cases $t(1\le t\le 100)$.

Each test case starts with $n(4\le n\le 7)$, the number of integers Elsie gives to Bessie.

The second line of each test case contains $n$ distinct integers $x_1,x_2,..,x_n$.

Output

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

Examples

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)$.