Minimum Coins for Candy

You are given several test cases. For each test case, you are given a set of coins and a target amount C. Your task is to determine the minimum number of coins needed to pay exactly C units. If it is not possible to pay exactly C units, output -1.

You can solve this problem using dynamic programming. Define the recurrence as follows:

$$dp[i] = \min_{\text{for all coins } coin \leq i} (dp[i - coin] + 1) $$

with the base condition:

$$dp[0] = 0.$$

inputFormat

The first line contains an integer T, the number of test cases. For each test case, the first line contains two integers N and C where N is the number of coin denominations and C is the target cost. The second line contains N space-separated integers representing the coin denominations.

outputFormat

For each test case, output a single line containing the minimum number of coins needed to pay exactly C. If it is not possible to pay exactly C using the given coins, output -1.

## sample

3
3 11
1 5 6
3 9
2 3 5
2 7
2 4

2
3
-1

</p>