줄 나누기

비행기에 타려고 승객 n명이 한 줄로 서 있다. 탑승구가 붐비지 않도록 이 줄을 앞에서부터 연속한 여러 조각으로 자른다. 크기가 3인 줄은 1+2, 2+1, 1+1+1, 3으로 자를 수 있다. 조각 크기가 같아도 순서가 다르면 다른 방법으로 세므로, 크기가 n인 줄을 자르는 방법은 모두 $2^{n-1}$가지다.

쓸 수 없는 조각 크기가 생기면 문제가 조금 어려워진다. 정수 m과 k가 주어질 때 등차수열 $m, m+k, m+2k, \dots$에 들어 있는 수는 조각 크기로 쓸 수 없다. 예를 들어 m이 0이고 k가 2이면 짝수 크기를 모두 쓸 수 없으므로, 크기가 4인 줄을 자르는 방법은 1+1+1+1, 1+3, 3+1의 3가지뿐이다.

모든 조각의 크기는 1 이상이다. 크기가 n인 줄을 이 조건에 맞게 자르는 방법의 수를 구하라.

첫째 줄에 테스트 케이스의 개수 t가 주어진다 ($1 \le t \le 10000$). 다음 t개 줄에는 각각 정수 n, m, k가 공백으로 구분되어 주어진다 ($1 \le n \le 30$, $0 \le m < k < 30$).

각 테스트 케이스마다 자르는 방법의 수를 한 줄에 하나씩 출력한다.