P7556 [USACO21OPEN] Do You Know Your ABCs? S

Farmer John’s cows are holding their daily meeting on the mooZ video conferencing platform. They have invented a simple number game to make the meeting more fun. Elsie has three positive integers $A$, $B$, and $C$ ($1\le A\le B\le C$). These numbers are secret, and she will not tell them directly to her sister Bessie. She tells Bessie $N$ ($4\le N\le 7$) distinct integers $x_1,x_2,\ldots,x_N$ ($1\le x_i\le 10^9$), and claims that each $x_i$ is one of $A$, $B$, $C$, $A+B$, $B+C$, $C+A$, or $A+B+C$. However, Elsie may be lying; these integers $x_i$ might not correspond to any valid $(A,B,C)$. Bessie cannot figure it out, so you need to compute the number of triples $(A,B,C)$ that are consistent with the numbers Elsie provided. Each input contains $T$ ($1\le T\le 100$) test cases that must be solved independently.

The first line of input contains $T$. For each test case, the first line contains $N$, the number of integers Elsie gave to Bessie. The second line of each test case contains $N$ distinct integers $x_1,x_2,\ldots,x_N$.

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

#### Sample Explanation For $x=\{4,5,7,9\}$, the five possible triples are: $$(2, 2, 5), (2, 3, 4), (2, 4, 5), (3, 4, 5), (4, 5, 7).$$ #### Test Point Properties - In test points $1 \sim 4$, all $x_i$ are at most $50$. - Test points $5 \sim 5$ satisfy $N=7$. - Test points $7 \sim 15$ have no additional constraints. #### Notes Problem author: Benjamin Qi. Translated by ChatGPT 5