教练希望他的队员们在跑体育场台阶时，每一步跨越一级或两级台阶，并满足以下规则：

a) 每条腿跨越两级台阶的次数相同。 b) 每条腿跨越一级台阶的次数相同。 c) 跨越两级台阶的总次数不小于跨越一级台阶的总次数。 d) 从左腿开始。

教练想知道，对于给定的（必然为偶数的）台阶总数，有多少种不同的跑法可以满足他的规则。

例如，对于六级台阶（每条腿各走三步），有 4 种可能性： $2211, 2112, 1221, 1122$（右腿跨越的步数以加粗字体显示）

对于八级台阶（每条腿各走四步），只有 1 种可能性，因为跨越两级台阶的次数必须至少与跨越一级台阶的次数一样多： $2222$

对于本题，你需要编写一个程序，计算满足教练四项准则的跑法总数。

输入格式

输入的第一行包含一个整数 $P$ ($1 \le P \le 10000$)，表示后续的数据集数量。每个数据集应被独立处理。

每个数据集由单行输入组成。它包含数据集编号 $K$，后跟一个偶数 $S$ ($2 \le S \le 100$)，表示需要跑的台阶总数。

输出格式

对于每个数据集，输出一行。输出行包含数据集编号 $K$，后跟一个空格，再后跟满足教练四项准则的跑法总数。

样例

样例输入 1

5
1 6
2 8
3 10
4 12
5 60

样例输出 1

1 4
2 1
3 9
4 37
5 40197719157