Đổi xu ít nhất

Tại quốc đảo Zeta chỉ lưu hành tiền xu. Có \(N\) loại xu, loại thứ \(i\) có mệnh giá \(C_i\) và mỗi loại có số lượng không giới hạn. Một du khách mang tới đó số tiền \(M\) và muốn đổi toàn bộ số tiền này thành xu địa phương sao cho tổng mệnh giá các đồng xu nhận được đúng bằng \(M\). Để túi đỡ nặng, ông muốn dùng ít đồng xu nhất có thể.

Cho các mệnh giá và số tiền \(M\), hãy tính số đồng xu tối thiểu cần dùng, hoặc báo không thể đổi được.

Input

• Dòng đầu chứa số nguyên \(T\) là số bộ dữ liệu.
• Mỗi bộ dữ liệu gồm hai dòng: dòng thứ nhất chứa hai số nguyên \(M\) và \(N\); dòng thứ hai chứa \(N\) số nguyên \(C_1, C_2, \dots, C_N\).

Output

Với mỗi bộ dữ liệu, in ra một dòng chứa số đồng xu tối thiểu; in \(-1\) nếu không thể đổi đúng \(M\).

Constraints

• \(1 \le T \le 100\)
• \(1 \le M \le 1000\)
• \(1 \le N \le 200\)
• \(1 \le C_i \le 200\)

Sample Input

2
11 3
5 4 1
7 2
4 6

Sample Output

3
-1

Explanation

Bộ 1: \(11 = 5 + 5 + 1\) cần \(3\) đồng xu (không có cách nào dùng ít hơn). Bộ 2: chỉ có xu \(4\) và \(6\) nên không thể tạo ra tổng lẻ \(7\), in \(-1\).