계단 뛰어오르기

코치는 선수가 경기장 계단을 한 번에 한 칸 또는 두 칸씩 밟아 뛰어오르기를 바란다. 규칙은 네 가지다.

1. 두 칸짜리 보폭의 개수가 왼발과 오른발에서 같다.
2. 한 칸짜리 보폭의 개수가 왼발과 오른발에서 같다.
3. 두 칸짜리 보폭의 총 개수가 한 칸짜리 보폭의 총 개수보다 적지 않다.
4. 왼발로 시작한다.

발은 왼발과 오른발을 번갈아 내딛고, 계단의 총 칸 수는 항상 짝수다. 규칙 1과 규칙 2 때문에 두 발이 밟는 칸 수는 서로 같다.

예를 들어 계단이 6칸이면 한 발이 3칸씩 담당하고, 방법은 4가지다. 오른발 보폭을 굵게 적으면 2211, 2112, 1221, 1122 이다. 계단이 8칸이면 두 칸짜리 보폭이 한 칸짜리 보폭보다 적을 수 없으므로 2222 한 가지뿐이다.

계단의 총 칸 수가 주어지면 네 규칙을 모두 만족하는 방법의 수를 구하라.

첫 줄에 데이터 집합의 개수 $P$가 주어진다 ($1 \le P \le 10000$).

이어지는 $P$개의 줄에는 각각 데이터 집합 번호 $K$와 뛰어오를 계단의 총 칸 수 $S$가 공백으로 구분되어 주어진다. $S$는 짝수이고 $2 \le S \le 100$이다. 각 데이터 집합은 서로 독립이며 같은 방식으로 처리한다.

각 데이터 집합마다 한 줄씩 출력한다. 한 줄에는 데이터 집합 번호 $K$, 공백 하나, 그리고 네 규칙을 모두 만족하는 방법의 수를 차례로 적는다.