Running Steps

Interview

Time limit1sMemory limit256 MB

Summary

Count left-right alternating sequences of one-step and two-step strides where both legs use equal counts and twos are at least as many as ones.

Level: Medium5 of 10
Topics: Combinatorics, Math
Solved: No attempts yet

Problem

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

Each leg takes the same number of two step strides.
Each leg takes the same number of one step strides.
The total number of two step strides is no smaller than the total number of one step strides.
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.

Input

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.

Output

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.

Examples4

Example 1

Input

Expected output

1 4
2 1
3 9
4 37
5 40197719157

Example 2
Input
```
1
1 2
```
Expected output
```
1 0
```
Example 3
Input
```
3
1 4
2 14
3 16
```
Expected output
```
1 1
2 16
3 101
```

Example 4

Input

Expected output