Description

Little bailey is a smart boy. Recently he invents a game. Given n types of balls, you must use minimum number of them to fill a box. The number of the balls are infinite. If the total volume of the balls in a box is equal to the volume of box, the box is filled. Bailey doesn't want to lose the game, so he asks you for help.

Input

The first line is an integer c which shows the number of cases. For each case there are 2 lines of positive integer as following: n V v1 v2 v3 ... vn n is the number of ball types, V is the volume of each box, and vi is the volume of ball type i (i=1,2,...,n).(1<=n<=20, 1<=vi<=V<=10^9)

Output

For each case print the minimum number of ball that can full fill the box. We promise there are must have a solution.

Sample Input

2 2 7 3 1 3 52 4 6 11

Sample Output

3 6

Source

HIT