Joy of Pokémon Observation

Time limit3sMemory limit2048 MB

Summary

For each habitat with total limb count t and up to three species with limb counts l_i, count the nonnegative integer solutions x_i of sum l_i x_i = t.

Level: Medium6 of 10
Topics: Number theory, Math, Combinatorics
Solved: No attempts yet

Problem

The Pokémon Conservation Society protects Pokémon and their habitats all around the globe. In recent research, data about $h$ habitats was collected. Each habitat may be inhabited by several Pokémon species. Researchers know how many limbs each species has. Pokémon are swift and extremely good at hiding, so researchers were only able to detect the total number of limbs in each habitat. Researchers understand that it might not be possible to find the population of each species, but would like to understand how much uncertainty is left. How many different combinations of Pokémon would have the observed number of limbs?

Input

The first line contains a single integer $h$ ( $1 \le h \le 1\,024$ ), the number of habitats. The next $h$ lines describe each habitat. Each line starts with two integers $t$ and $s$ ( $0 \le t \le 10^9$ , $1 \le s \le 3$ ), where $t$ is the total number of limbs and $s$ is the number of species in the habitat. They are followed by $s$ integers $l_i$ ( $1 \le l_i \le 16$ ), the number of limbs for each species.

Output

Output the number of possible combinations of Pokémon in each habitat. Output $h$ lines, each containing a single integer.

Examples2

Example 1
Input
```
3
6 1 3
6 2 2 3
6 3 1 2 3
```
Expected output
```
1
2
7
```

Example 2

Input

4
1000000000 3 1 1 1
0 3 2 4 5
17 2 2 4
34 3 5 3 2

Expected output

500000001500000001
1
0
25