수 분할

Shekhu에게는 N개의 공이 있다. 그녀는 다음 제약 조건을 모두 만족하는 방식으로 공을 하나 이상의 양동이에 나누어 담으려고 한다.

• 왼쪽에서 오른쪽으로 읽을 때 양동이에 든 공의 수는 비감소 순서여야 한다.

• 가장 왼쪽 양동이는 비어 있지 않아야 하며, 가장 왼쪽 양동이에 든 공의 수는 D로 나누어떨어져야 한다.

• 임의의 두 양동이(서로 인접한 두 양동이에만 국한되지 않음)에 든 공의 수의 차이는 2 이하여야 한다.

Shekhu가 이를 수행하는 서로 다른 방법은 몇 가지인가? 왼쪽에서 오른쪽으로 읽은 각 양동이의 공 개수 목록이 다르면 두 방법은 서로 다른 것으로 간주한다.

제한

1 ≤ T ≤ 100. 테스트 세트별 시간 제한: 30초. 메모리 제한: 1GB. 1 ≤ D ≤ 100.

작은 데이터 세트(테스트 세트 1 - 공개)

1 ≤ N ≤ 2000.

큰 데이터 세트(테스트 세트 2 - 비공개)

1 ≤ N ≤ $10^{5}$.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 위에서 설명한 두 정수 N과 D가 있는 한 줄로 구성된다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y은 위에서 설명한 답이다.

예제 케이스 #1에서 가능한 분배 방법은 다음과 같다.

• 1 1 1 1 1 1 1

• 1 1 1 1 1 2

• 1 1 1 1 3

• 1 1 1 2 2

• 1 2 2 2

• 1 1 2 3

• 1 3 3

• 2 2 3

• 3 4

• 7

1과 4의 차이가 2보다 크므로, 1 2 4은 유효한 분배 방법이 아님에 유의한다.

예제 케이스 #2에서 가능한 분배 방법은 다음과 같다.

• 2 2 3

첫 번째 항이 2로 나누어떨어지지 않으므로, 3 4은 가능하지 않다.

예제 케이스 #3에서는 가능한 배열이 존재하지 않는다.