Problem D
Volume Amplification

Image by audiophilia.

You have a bunch of audio amplifiers which you have been given by your uncle, who has too much stuff lying around. An amplifier takes an audio signal as input and produces the same signal frequencies as output, but with a possibly different volume level. It multiplies the input signal by some constant factor to produce its output. You want to string them together in sequence to produce a desired volume level for your speakers. Using each amplifier at most once, how close can you get, without going over your desired volume?

For example, suppose that your music player is producing a volume level of $1$, and you want to amplify this signal to a volume level of $80$. You have three amplifiers that multiply the volume input to them by factors of $3$, $10$, or $8$, respectively. If you use the latter two amplifiers in sequence, it will produce the desired volume level. However, if your desired volume level was $35$, then the closest you can get is $30$.

Input

The first line of input contains an integer $0 \le n \le 10$ indicating the number of test cases that follow. Each test case has two lines. The first line contains two integers $1 \le a \le 100$ and $1 \le y \le 10\, 000\, 000$, indicating the number of amplifiers and the target amplification, respectively. The second line contains $a$ amplifier descriptions, given as space-separated integers. Each amplifier description is an integer in the range $[1,100]$, indicating the amplifier’s multiplication factor.

Output

Assume that the output from your music player is at volume level $1$. For each test case with goal amplification $y$, give the closest output level you can achieve that is $\le y$ using a series of $0$ or more amplifiers.

2
3 80
3 10 8
3 35
3 10 8

80
30