Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

Problem hidden on 2012-06-16 10:32:46 by :D

EINST - Is he smart or is he smart

no tags 

 

 

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)

Added by:Ali Asgar
Date:2011-10-15
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64