Description

最近实验室新买了一个天平，为了能更好的测量还要采购一些砝码。但是为了能提高砝码的利用率，要求买N个砝码，它们的总重量为M，并且能根据所买的砝码组合出所有小于M的重量。现在请问有多少种采购方案。因为方案总数可能很大，请对4294967296取余。

Input

首先输入一个整数T（T<=30）表示有T组数据，接下来T行，每行两个整数N,M（N,M<=200）表示要买N个砝码，砝码总重量为M。

Output

对于每组数据 输出有多少种方案。

Sample

Input

3
3 5
2 4
4 7

Output

2
0
3

Hint

样例3的三种方案分别为 ： 1 1 1 4， 1 1 2 3， 1 2 2 2，

Source: Xenocide