공 나누어 담기

셰쿠에게 공 $N$개가 있다. 이 공을 양동이 한 개 이상에 나누어 담으려고 하는데, 다음 조건을 모두 만족해야 한다.

1. 양동이에 담긴 공의 개수는 왼쪽에서 오른쪽으로 읽을 때 감소하지 않아야 한다.
2. 가장 왼쪽 양동이는 비어 있으면 안 되고, 그 양동이에 담긴 공의 개수는 $D$의 배수여야 한다.
3. 인접한 두 양동이뿐 아니라 임의의 두 양동이에 담긴 공의 개수 차이가 2 이하여야 한다.

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

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

다음 $T$개의 줄에 테스트 케이스가 한 줄에 하나씩 주어진다. 각 줄에는 두 정수 $N$과 $D$가 공백으로 구분되어 주어진다.

제한

• $1 \le T \le 100$
• $1 \le D \le 100$
• $1 \le N \le 2000$

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 테스트 케이스 번호(1부터 시작)이고, $y$는 나누어 담는 방법의 수이다.

$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보다 크므로 세지 않는다.

$N = 7$, $D = 2$이면 가능한 방법은 2 2 3 하나뿐이다. 3 4는 첫 양동이의 공 개수 3이 2의 배수가 아니라서 제외된다.

$N = 2$, $D = 4$이면 가능한 방법이 없다.