Mr. Frodo and Samwise Gamjee are on their quest to find "The Magical ring".

But the path to "The ring" isn't easy.They are now stuck in their way because of N metre long river.

Fortunately,there is a shop which has infinite supply of wooden logs of specific lengths but each piece of wooden log has same price irrespective of their length.

As Samwise isn't interested in spending a lot so he wants to know the minimum number of logs he should buy that should be enough to make them cross the N metre long river.He isn't even sure whether they can cross the river by using logs of available length as the shopkeeper won't give them wooden logs if any of the log is not fully used.

Can you help him?

INPUT:

1st line contains T- no. of test cases 1st line of each test case contains N-the length of river in metre. 2nd line of each test case contains M-the number of different length of log available in that shop. Next line contains M-space distinct integers A_i each specifying the length of wooden log in metre available in that shop.

OUTPUT:

For each test case,output a single line containing the minimum number of logs needed to cross the river of N metre length.Output "-1" if they are unable to cross the river using log of available lengths.

CONSTRAINTS

1<=T<=10

1<=N<=500

1<=M<=500

1<=A_i<=500