[DSA-QuayLui-NhanhCan].Máy ATM.

Một máy ATM hiện có n (n ≤ 30) tờ tiền có giá trị t[1], t[2], …, t[n]. Hãy tìm cách trả ít tờ nhất với số tiền đúng bằng S (các tờ tiền có giá trị bất kỳ và có thể bằng nhau, mỗi tờ tiền chỉ được dùng một lần).

Input Format

Dòng đầu tiên ghi số bộ test T (T<10). Mỗi bộ test gồm 2 số nguyên n và S (S ≤ 10^9). Dòng thứ hai chứa n số nguyên t[1], t[2], …, t[n] (t[i] ≤ 10^9)

Constraints

.

Output Format

Với mỗi bộ test ghi ra số tờ tiền ít nhất phải trả.Nếu không thể tìm được kết quả, in ra -1.

Ví dụ:

Dữ liệu vào

1
3 5
1 4 5

Dữ liệu ra

1