Albert Einstein, being as smart as he is, cannot seem to make coin change. 

He's spending all his time trying to find an optimal set of denominations instead of proving the theory of relativity. He needs your help! Find out how can a given amount of money be made with the least number of coins of given denominations?

Input

The first line holds T denoting the number of test cases. This is followed by T lines, each containing the following.

X N a1 a2 a3… an

X is the amount to be made.

N is the number of denominations

a1 a2… an are the denominations themselves.

1 <= T <= 10

0 <= X <= 10000

1 <= N <= 100

1 <= ai <= 10000

Note: Each denomination can be used more than once.

Output

For each case, output the minimum number of coins required to make the sum X given its denominations.

Output "No solution" without the quotes if the value X cannot be obtained using the given denominations.

Example

Input:
4

6 3 4 3 1

10 2 8 1 

0 2 10 12

1 2 12 34

Output:

2

3

0

No solution

Explanation:

6 = 3 + 3 (Requiring a minimum of two coins as opposed to 4 + 1 + 1 which would require 3 coins)

10 = 8 + 1 + 1 (Requiring a minimum of three coins)

0 (Requires no coins and hence the solution is 0)

1 (Cannot be obtained using the denominations 12 and 34)