버스 노선

Bucket은 버스를 타고 시골을 가로지르는 매우 긴 여행을 계획하고 있다. 그녀의 여행은 N개의 버스 노선으로 이루어져 있으며, 반드시 타야 하는 순서대로 1부터 N까지 번호가 매겨져 있다. 버스 자체는 매우 빠르지만 자주 운행하지 않는다. i번째 버스 노선은 $X_{i}$일마다 한 번만 운행한다.

더 구체적으로 말하면, 그녀는 i번째 버스를 $X_{i}$일, 2X_{i}일, 3X_{i}일 등에만 탈 수 있다. 버스는 매우 빠르므로 같은 날에 여러 버스를 탈 수 있다.

Bucket은 D일까지 여행을 마쳐야 하지만, 가능한 한 늦게 여행을 시작하고 싶다. D일까지 여행을 마치면서 첫 번째 버스를 탈 수 있는 가장 늦은 날은 언제인가?

Bucket이 D일까지 여행을 마치는 것이 가능함이 보장된다.

제한

시간 제한: 10초. 메모리 제한: 1 GB. 1 ≤ T ≤ 100. 1 ≤ $X_{i}$ ≤ D. 1 ≤ N ≤ 1000. Bucket이 D일까지 여행을 마치는 것이 가능함이 보장된다.

테스트 세트 1

1 ≤ D ≤ 100.

테스트 세트 2

1 ≤ D ≤ $10^{12}$.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 두 정수 N과 D를 포함하는 줄로 시작한다. 그다음 줄에는 N개의 정수가 주어지며, i번째 정수는 $X_{i}$이다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x은 테스트 케이스 번호이고(1부터 시작), y은 D일까지 여행을 마치면서 첫 번째 버스를 탈 수 있는 가장 늦은 날이다.

예제 케이스 #1에는 N = 3개의 버스 노선이 있으며, Bucket은 D = 10일까지 도착해야 한다. 그녀는 다음과 같이 할 수 있다.

• 1st 버스를 6일에 탄다 ($X_{1}$ = 3),

• 2nd 버스를 7일에 탄다 ($X_{2}$ = 7) 그리고

• 3rd 버스를 8일에 탄다 ($X_{3}$ = 2).

예제 케이스 #2에는 N = 4개의 버스 노선이 있으며, Bucket은 D = 100일까지 도착해야 한다. 그녀는 다음과 같이 할 수 있다.

• 1st 버스를 99일에 탄다 ($X_{1}$ = 11),

• 2nd 버스를 100일에 탄다 ($X_{2}$ = 10),

• 3rd 버스를 100일에 탄다 ($X_{3}$ = 5) 그리고

• 4th 버스를 100일에 탄다 ($X_{4}$ = 50),

예제 케이스 #3에는 N = 1개의 버스 노선이 있으며, Bucket은 D = 1일까지 도착해야 한다. 그녀는 다음과 같이 할 수 있다.

• 1st 버스를 1일에 탄다 ($X_{1}$ = 1).