## USACO 2021 US Open, Silver

## Problem 2. Do You Know Your ABCs?

Contest has ended.

**Log in to allow submissions in analysis mode**

Elsie has three positive integers $A$, $B$, and $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$ ($4\le N\le 7$) distinct integers $x_1,x_2,\ldots,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$, or $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).

Each input file will contain $T$ ($1\le T\le 100$) test cases that should be solved independently.

#### INPUT FORMAT (input arrives from the terminal / stdin):

The first input line contains $T$.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 $x_1,x_2,\ldots,x_N$.

#### OUTPUT FORMAT (print output to the terminal / stdout):

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

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

#### SAMPLE OUTPUT:

1 3 5 1 4 3 0 0 0 1

For $x=\{4,5,7,9\}$, the five possible triples are as follows:

#### SCORING:

- In test cases 1-4, all $x_i$ are at most $50$.
- Test cases 5-6 satisfy $N=7$.
- Test cases 7-15 satisfy no additional constraints.

Problem credits: Benjamin Qi