Minimum Coin Change

This problem involves determining the minimum number of coins needed to make up a given amount. You are given an integer amount and a list of available coin denominations. The goal is to compute the minimum number of coins required such that their sum equals the given amount. If it is not possible to form the amount using the provided denominations, output -1.

The problem can be formulated using dynamic programming. Define \(dp[i]\) as the minimum number of coins required to achieve a sum of \(i\). The recurrence relation is given by:

\[ \; dp[i] = \min_{c \in \text{coins}} \{ dp[i - c] + 1 \} \quad \text{for } i \geq c \]

with the base condition \(dp[0] = 0\). Your task is to implement an efficient solution that reads input from stdin and prints the results to stdout.

inputFormat

The first line contains an integer T, the number of test cases. Each test case is described as follows:

• The first line of each test case contains two integers: amount and n, where n is the number of different coin denominations.
• The second line contains n space-separated integers representing the coin denominations.

All input is read from stdin.

outputFormat

For each test case, print the minimum number of coins needed to obtain the given amount on a separate line. If it is not possible, print -1. All output should be written to stdout.

## sample

1
11 3
1 5 10

2

</p>