Farmer John's cows are collected daily on the "mooZ" video platform. They came up with a simple number game.
Elsa has three positive integers A, B, C (1≤A≤B≤C). They are supposed to be secret, which is why she doesn't explicitly announce them to her sister, Besi. Instead, she tells Besi N (4≤N≤7) distinct integers x
1,x
2,…,x
N (1&le ;x
i≤10
9), meaning that each of xi is one of the numbers A, B, C, A+B, B+C, C+A, or A+B+C. However, Elsa can lie. Integers xi may not correspond to any valid triple (A,B,C).
Besi asked you to determine the number of triplets (A,B,C) corresponding to the numbers Elsa presented (possibly 0).
Each input file will contain T (1≤T≤100) tests that need to be processed independently.
INPUT FORMAT
The first line contains an integer T.
Each test starts with the number N, the number of integers that Elsa gave to Besi.
The second line of each test contains N distinct integers x
1,x
2,…,x
N.
OUTPUT FORMAT
For each test case print the number of triples (A,B,C) corresponding to the numbers presented by Elsa.
Examples
| # |
Input |
Output |
Explanation |
| 1 |
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 |
For x={4,5,7,9}, there are 5 possible combinations:
(2,2,5),(2,3,4),(2,4,5),(3,4,5),(4,5,7). |