Minimum Coins for Tax Payment

You are given a tax amount \(N\) (in quads) and a set of coin denominations. Your task is to compute the minimum number of coins required to pay exactly \(N\) quads. If it is impossible to reach exactly \(N\) using the available coins, output -1.

This is a classic coin change problem which can be solved using dynamic programming. The recurrence used is:

\(dp[j] = \min_{coin}\{ dp[j],\ dp[j-coin] + 1 \}\) for each coin such that \(coin \leq j\), with \(dp[0] = 0\) and \(dp[j] = \infty\) for \(j > 0\) initially.

Read the input from standard input and output the result for each test case to standard output.

inputFormat

The first line of input contains an integer \(T\) representing the number of test cases. Each test case consists of two lines:

• The first line contains an integer \(N\) denoting the tax amount to be paid.
• The second line contains a space-separated list of integers representing the available coin denominations.

Note: When there is more than one test case within the same input, they are processed sequentially.

outputFormat

For each test case, output a single line containing the minimum number of coins needed to exactly pay \(N\). If it is not possible, output -1.

## sample

2
11
1 5 10
15
2 3 5

2
3

</p>