#include <iostream>
#include <climits>
using namespace std;
int minCoins(int coins[], int n, int V) {
int dp[V + 1];
// Base case
dp[0] = 0;
// Initialize all table values as Infinite
for (int i = 1; i <= V; i++)
dp[i] = INT_MAX;
// Compute minimum coins required for all
// values from 1 to V
for (int i = 1; i <= V; i++) {
// Go through all coins smaller than i
for (int j = 0; j < n; j++)
if (coins[j] <= i) {
int sub_res = dp[i - coins[j]];
if (sub_res != INT_MAX && sub_res + 1 < dp[i])
dp[i] = sub_res + 1;
}
}
return (dp[V] == INT_MAX) ? -1 : dp[V];
}
int main() {
int T;
cin >> T;
while (T--) {
int V, N;
cin >> V >> N;
int coins[N];
for (int i = 0; i < N; i++)
cin >> coins[i];
cout << minCoins(coins, N, V) << endl;
}
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8Y2xpbWl0cz4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmludCBtaW5Db2lucyhpbnQgY29pbnNbXSwgaW50IG4sIGludCBWKSB7CiAgICBpbnQgZHBbViArIDFdOwoKICAgIC8vIEJhc2UgY2FzZQogICAgZHBbMF0gPSAwOwoKICAgIC8vIEluaXRpYWxpemUgYWxsIHRhYmxlIHZhbHVlcyBhcyBJbmZpbml0ZQogICAgZm9yIChpbnQgaSA9IDE7IGkgPD0gVjsgaSsrKQogICAgICAgIGRwW2ldID0gSU5UX01BWDsKCiAgICAvLyBDb21wdXRlIG1pbmltdW0gY29pbnMgcmVxdWlyZWQgZm9yIGFsbAogICAgLy8gdmFsdWVzIGZyb20gMSB0byBWCiAgICBmb3IgKGludCBpID0gMTsgaSA8PSBWOyBpKyspIHsKICAgICAgICAvLyBHbyB0aHJvdWdoIGFsbCBjb2lucyBzbWFsbGVyIHRoYW4gaQogICAgICAgIGZvciAoaW50IGogPSAwOyBqIDwgbjsgaisrKQogICAgICAgICAgICBpZiAoY29pbnNbal0gPD0gaSkgewogICAgICAgICAgICAgICAgaW50IHN1Yl9yZXMgPSBkcFtpIC0gY29pbnNbal1dOwogICAgICAgICAgICAgICAgaWYgKHN1Yl9yZXMgIT0gSU5UX01BWCAmJiBzdWJfcmVzICsgMSA8IGRwW2ldKQogICAgICAgICAgICAgICAgICAgIGRwW2ldID0gc3ViX3JlcyArIDE7CiAgICAgICAgICAgIH0KICAgIH0KICAgIHJldHVybiAoZHBbVl0gPT0gSU5UX01BWCkgPyAtMSA6IGRwW1ZdOwp9CgppbnQgbWFpbigpIHsKICAgIGludCBUOwogICAgY2luID4+IFQ7CiAgICB3aGlsZSAoVC0tKSB7CiAgICAgICAgaW50IFYsIE47CiAgICAgICAgY2luID4+IFYgPj4gTjsKICAgICAgICBpbnQgY29pbnNbTl07CiAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCBOOyBpKyspCiAgICAgICAgICAgIGNpbiA+PiBjb2luc1tpXTsKICAgICAgICBjb3V0IDw8IG1pbkNvaW5zKGNvaW5zLCBOLCBWKSA8PCBlbmRsOwogICAgfQogICAgcmV0dXJuIDA7Cn0K