시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 114 41 27 38.028%

문제

청계천 근처에 사는 사람들의 주된 주말 취미는 청계천을 산책하면서 마가리타를 마시는 것이다. 청계천은 사람들이 사는 아파트(청계천엔 아파트가 하나)에서 시작해서 규현치킨에서 끝난다. 마가리타는 이 청계천을 따라 걷는 중에 보이는 가판대에서 살 수 있다.

마가리타의 가격은 재료의 양과 품질, 그리고 가판대의 분위기에 따라서 다르다. 마침 오늘 승환이가 청계천 근처로 이사왔고, 이 취미를 한 번 따라해 보려고 한다. 오늘은 승환이가 이사온 날이기 때문에, 서로 다른 마가리타의 맛을 느껴보려고 한다.

각 가판대에서 파는 마가리타 한 잔의 가격이 주어졌을 때, 승환이가 맛을 느낄 수 있는 서로 다른 마가리타의 조합이 몇 개나 되는지 계산해보려고 한다. 

승환이는 각각의 가판대에서 마가리타를 많아야 한 잔만 살 수있다. 그리고, 승환이가 쓴 돈은 자신이 가지고 있는 돈의 양을 넘을 수 없고, 남은 돈으로는 구매하지 않은 그 어떤 마가리타도 살 수 없어야 한다. 

예를 들어, 승환이가 지금 25만원을 가지고 있고, 각각의 가판대에서 파는 마가리타 한 잔의 가격이 다음과 같다고 하자.

  • A: 8만원
  • B: 9만원
  • C: 8만원
  • D: 7만원
  • H: 16만원
  • J: 5만원

위의 조건을 만족하면서, 승환이가 맛을 느낄 수 있는 마가리타의 조합은 다음과 같다.

ABC(25), ABD(24), ABJ(22), ACD(23), ACJ(21), ADJ( 20), AH(24), BCD(24), BCJ(22), BDJ(21), BH(25), CDJ(20), CH(24), DH(23), HJ(21)

따라서, 승환이가 맛을 볼 수 있는 마가리타의 조합은 총 15가지이다.

입력

첫째 줄에 테스트 케이스의 개수 T(1<=T<=1,000)가 주어진다. 각 테스트 케이스는 두 줄로 이루어져 있다. 첫째 줄에는 가판대의 개수 V(1<=V<=30)와 승환이가 가지고 있는 돈의 양 D(1<=D<=1,000)가 주어진다. 두 값은 공백으로 구분되어 있다. 둘째 줄에는 각 가판대에서 파는 마가리타 한 잔의 양이 주어진다.

문제에서 주어지는 돈의 양은 모두 만원 단위이다. 따라서, 승환이가 가지고 있는 돈이 10이라면, 이는 10만원이다. 또, 마가리타 한 잔의 가격이 2라면, 2만원과 같다.

출력

각 테스트 케이스에 대해, 승환이가 맛 볼 수 있는 마가리타 조합의 개수를 출력한다.

예제 입력

2
6 25
8 9 8 7 16 5
30 250
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

예제 출력

15
16509438

힌트