분할 수 세기 (라지)

셰쿠에게 공 $N$개가 있다. 셰쿠는 이 공을 바구니 한 개 이상에 나누어 담으려고 하며, 다음 조건을 모두 지켜야 한다.

1. 바구니를 왼쪽에서 오른쪽으로 읽을 때 각 바구니에 담긴 공의 개수가 비내림차순이어야 한다.
2. 가장 왼쪽 바구니는 비어 있으면 안 되고, 그 바구니에 담긴 공의 개수는 $D$의 배수여야 한다.
3. 인접한 두 바구니뿐 아니라 임의의 두 바구니에 대해, 담긴 공 개수의 차이가 2 이하여야 한다.

셰쿠가 공을 나누어 담는 방법은 몇 가지인가? 왼쪽에서 오른쪽으로 읽은 공 개수의 목록이 다르면 서로 다른 방법으로 센다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다.

다음 $T$개의 줄에 각각 두 정수 $N$과 $D$가 주어진다.

제한

• $1 \le T \le 100$
• $1 \le D \le 100$
• $1 \le N \le 10^5$

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 공을 나누어 담는 방법의 수이다. 답은 32비트 정수 범위를 넘을 수 있다.

예제 1의 첫 번째 테스트 케이스 ($N = 7$, $D = 1$)에서 가능한 분배는 다음 10가지다.

• 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 2 4는 1과 4의 차이가 2보다 크므로 올바른 분배가 아니다.

예제 1의 두 번째 테스트 케이스 ($N = 7$, $D = 2$)에서 가능한 분배는 2 2 3 하나뿐이다. 3 4는 첫 항이 2의 배수가 아니라서 안 된다.

예제 1의 세 번째 테스트 케이스 ($N = 2$, $D = 4$)에서는 가능한 분배가 없다.