Ở đất nước Omega người ta chỉ tiêu tiền xu. Có $N$ loại tiền xu, loại thứ $i$ có mệnh giá là $C_i$ đồng, số lượng mỗi loại rất lớn. Một người khách du lịch đến Omega du lịch với số tiền $M$ đồng. Ông ta muốn đổi số tiền đó ra tiền xu Omega để tiện tiêu dùng. Ông ta cũng muốn số đồng tiền đổi được là ít nhất (cho túi tiền đỡ nặng khi đi đây đi đó). Bạn hãy giúp ông ta tìm cách đổi tiền.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên $T$ biểu thị tổng số trường hợp kiểm tra.
• Dòng đầu tiên của mỗi trường hợp thử nghiệm là $M$ và $N$.
• Dòng thứ hai của mỗi trường hợp thử nghiệm chứa giá trị của $N$ đồng tiền $C_1,C_2...C_n$

Dữ liệu ra

• Mỗi trường hợp in một dòng là số lượng xu tối thiểu để thực hiện thay đổi, nếu không thể in "-1".

Ràng buộc

• $1\le T\le 100$
• $1\le M\le 1000$
• $1\le N\le 200$
• $1\le C_i\le 200$

Input 1

1
7 2
2 1

Output 1

4