Farmer John 的奶牛正在 mooZ 视频会议平台上举行每日集会。
她们发明了一个简单的数字游戏,为会议增添一些乐趣。
Elsie 有三个正整数 A、B 和 C。
这些数字是保密的,她不会直接透露给她的姐妹 Bessie。
她告诉 Bessie N 个不同的整数 x1,x2,…,xN,并宣称每一个 xixi 都是 A、B、C、A+B、B+C、C+A 或 A+B+C之一。
然而,Elsie 可能在撒谎;这些整数 xi 可能并没有对应任何一组合法的 (A,B,C)。
Bessie 百思不得其解,所以需要靠你来求出与 Elsie 给出的数相符合的三元组 (A,B,C) 的数量。
输入的第一行包含 T,表示共有 T 个测试用例。
每个测试用例的第一行包含 N,为 Elsie 给 Bessie 的整数的数量。
每个测试用例的第二行包含 N 个不同的整数 x1,x2,…,xN.
对于每个测试用例,输出与 Elsie 给出的数相符合的三元组 (A,B,C) 的数量。
1≤T≤100
1≤A≤B≤C
4≤N≤7
1≤xi≤109
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≤A≤B≤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≤N≤7) distinct integers x1,x2,…,xN (1≤xi≤109), claiming that each xi is one of A, B, C, A+B, B+C, C+A, or A+B+C. However, Elsie may be lying; the integers xi 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≤T≤100) test cases that should be solved independently.
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 x1,x2,…,xN.
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}, the five possible triples are as follows: