수수께끼

엘레오노라의 할머니 서차(Sercha)는 손주들에게 수학 수수께끼 내기를 좋아합니다. 지난 가족 여행에서 할머니는 이런 문제를 냈습니다.

"어떤 가게가 $1$부터 $K$까지의 가격이 매겨진 상품을 판다고 하자. 나는 $N$개의 동전을 가지고 있고, 그 액면가는 순서대로 $A_1, A_2, \ldots, A_N$ 이란다. 나는 나이가 많아 되도록 적은 수의 동전만 챙기고 싶구나. $A_1$부터 하나씩 순서대로 동전을 챙긴다고 할 때, 앞에서부터 몇 개를 챙기면 챙긴 동전들의 부분집합으로 $1$부터 $K$까지의 모든 가격을 정확히 지불할 수 있겠니?"

엘레오노라는 몇 초 만에 답을 말하고는 생각했습니다. "이런 기본적인 알고리즘쯤은 이제 쉬워요!"

엘레오노라를 도와주세요. 주어진 순서대로 앞에서부터 동전을 챙길 때, 챙긴 동전들의 부분집합의 합으로 $1$부터 $K$까지의 모든 금액을 만들 수 있게 되는 데 필요한 최소 동전 개수를 구하세요. $N$개를 모두 챙겨도 불가능하면 $-1$을 출력합니다.

첫 줄에 테스트 케이스의 수 $T$가 주어집니다.

각 테스트 케이스의 첫째 줄에는 두 정수 $N$과 $K$가 주어집니다 ($N \le 100000$, $K \le 1000000$). 둘째 줄에는 $N$개의 동전 액면가 $A_1, A_2, \ldots, A_N$이 순서대로 공백으로 구분되어 주어집니다 ($A_i \le 100000$).

각 테스트 케이스마다, 앞에서부터 순서대로 동전을 챙길 때 $1$부터 $K$까지의 모든 가격을 챙긴 동전들의 부분집합의 합으로 지불할 수 있게 하기 위해 챙겨야 하는 최소 동전 개수를 한 줄에 출력합니다. $N$개를 모두 챙겨도 불가능하면 $-1$을 출력합니다.