Counting Coin Combinations

You are given a target sum \(T\) and a list of distinct coin denominations \(C = \{c_1, c_2, \dots, c_n\}\). Your task is to count the number of unique combinations (i.e. subsets) of coins that sum exactly to \(T\). Each coin can be used at most once in a combination.

Note: Two combinations are considered different if they contain a different set of coin values. The order of coins does not matter.

Example:

• For \(T = 15\) and \(C = [5, 10, 12]\), there is exactly 1 valid combination: [5, 10].
• For \(T = 10\) and \(C = [2, 3, 7, 8]\), there are 2 valid combinations: [2, 8] and [3, 7].

inputFormat

The first line of input contains an integer \(T\), representing the number of test cases.

For each test case:

• The first line contains two integers: the target sum and the number of coins.
• The second line contains the list of coin denominations separated by spaces.

outputFormat

For each test case, output a single line that contains the number of unique combinations of coins which sum up exactly to the target value.

## sample

2
10 4
2 3 7 8
15 3
5 10 12

2
1

</p>