描述

在电视游戏节目《角斗士》中，最终的竞赛是穿越一个障碍赛跑的赛道。为了有所变化，制片人决定每周改变赛道。赛道总是由(m)个高度各不相同的障碍物组成，这些障碍物沿着一条直线放置。一个障碍物由两个最初相连的平台组成，这两个平台可能会分开。在一个障碍物的两个平台之间，可能会放置其他更高的障碍物。而且，障碍物可能会一个接一个地放置。

制片人认为最理想的情况是不同周的比赛结果能够相互比较。因此，他希望建造难度相似的赛道。

一个提议的难度衡量标准是在赛道上高于其紧邻的前一个平台的平台数量。此外，赛道最左边（第一个）的平台总是计一分，因为它位于地面之上。例如，图1中右边的赛道难度为4分。

你的任务是找出使用给定数量的障碍物构建出具有给定难度分数的赛道有多少种方法。

输入

输入的第一行是一个正整数(n)，表示接下来的测试场景数量。每个测试场景由一行组成，包含两个非负整数(m)和(k)，其中(m \leq 50)表示障碍物的数量，(k)是所要求的难度分数。

输出

对于每个测试场景，输出一行，包含一个正整数，表示使用(m)个障碍物构建出难度恰好为(k)的不同赛道的数量。你可以放心地假设答案小于(10^{100})。

输入数据 1

6
1 0
1 1
2 1
2 2
3 1
3 2

输出数据 1

0
1
1
2
1
8

来源

2003年西北欧赛