Running Steps

A coach wants his runners to climb the stadium steps one or two steps at a time, under four rules.

1. Each leg takes the same number of two step strides.
2. Each leg takes the same number of one step strides.
3. The total number of two step strides is no smaller than the total number of one step strides.
4. The run starts with the left leg.

The legs alternate, and the total number of steps is always even. Rules 1 and 2 force the two legs to cover the same number of steps.

With six steps, each leg covers three, and there are 4 ways. Writing the right leg strides in bold: 2211, 2112, 1221, 1122. With eight steps there is only one way, 2222, because the two step strides cannot be outnumbered by the one step strides.

Given the total number of steps, count the ways to run them that satisfy all four rules.

The first line contains the number of data sets $P$ ($1 \le P \le 10000$).

Each of the next $P$ lines contains a data set number $K$ and the total number of steps $S$, separated by a space. $S$ is even and $2 \le S \le 100$. Every data set is independent and is processed the same way.

Print one line per data set. Each line holds the data set number $K$, a single space, and the number of ways to run the steps that satisfy all four rules.