ABC 어렵게 맞추기 (Do You Know Your ABCs?)

A, B, C (1≤A≤B≤C)를 맞추는 게임을 해보자.

규칙은 단순하다 1…10^9의 범위에 해당하는 정수 N 개가 주어진다.

각 N 개의 정수는 A, B, C, A+B, B+C, C+A, A+B+C 중 하나인데, 순서는 무작위로 주어진다.

다만, 주어지는 모든 정수가 꼭 위에서 말한 조건대로 나오는 것은 아니다. 거짓된 수가 들어오는 경우도 있다.

언제나 유일한 정답이 나오는 것이 보장되니 A, B, C를 맞춰보자.

참고로 게임은 총 T번 진행된다.

입력

첫 줄에 테스트케이스의 수 T가 주어진다. (1 ≤ T ≤ 100)

각 테스트 케이스의 첫 번째 줄에 N이 주어진다. (4 ≤ N ≤ 7)

각 테스트 케이스의 N개의 정수 x_1,x_2,…,x_N가 주어진다. (1≤x_i≤10^9)

출력

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

예제1

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

출처

USACO 2021 US Open Silver

ABC 어렵게 맞추기 (Do You Know Your ABCs?) 1초 512MB