토끼 개체 수

가상의 토끼 개체군이 다음 규칙을 따른다.

1. 첫째 달에는 갓 태어난 토끼 한 쌍만 있다.
2. 한 쌍은 태어난 다음 달부터 짝짓기를 할 수 있다.
3. 짝짓기를 할 수 있는 쌍은 매달 짝짓기를 한다.
4. 짝짓기를 한 쌍은 그다음 달에 암수 한 쌍을 낳는다.
5. 한 쌍은 나이가 $D$개월이 되는 달까지 살고, 나이가 $R$개월을 넘으면 더 번식하지 않는다. $R \le D$이다.

나이는 태어난 달에 1개월이고 달마다 1씩 늘어난다. 그래서 $b$번째 달에 태어난 쌍은 $b$번째 달부터 $b + D - 1$번째 달까지 살아 있고, 나이가 2 이상 $R$ 이하인 달, 곧 $b + 1$번째 달부터 $b + R - 1$번째 달까지 매달 짝짓기를 한다.

$D = 3$, $R = 3$인 경우를 보자. 한 쌍은 세 달을 살고 짝짓기를 두 번 한다. 처음 한 쌍은 첫째 달에 태어나 둘째 달에 짝짓기를 하고, 셋째 달에 첫 자식 쌍이 태어난다. 이 쌍은 셋째 달에 다시 짝짓기를 해서 넷째 달에 두 번째 자식 쌍을 낳는다. 처음 한 쌍은 넷째 달에 죽으므로 넷째 달의 개체 수에는 들어가지 않는다.

$D$, $R$, $M$이 주어졌을 때 $M$번째 달에 살아 있는 토끼 쌍의 수를 구하는 프로그램을 작성하시오.

첫째 줄에 테스트 케이스의 개수 $N$이 주어진다 ($1 \le N \le 100$). 다음 $N$개의 줄에는 각각 세 양의 정수 $D$, $R$, $M$이 주어진다. $D$는 한 쌍이 죽는 나이, $R$은 번식을 멈추는 나이, $M$은 개체 수를 구할 달이다. $D \le 100$, $R \le 100$, $M \le 20$, $R \le D$이다.

각 테스트 케이스마다 Case #n: k 형식으로 한 줄씩 출력한다. $n$은 1부터 시작하는 테스트 케이스 번호이고, $k$는 $M$번째 달에 살아 있는 토끼 쌍의 수이다.