A triangle tower consist of floors. The ith floor has 2i-1 small triangles, each small triangle has an integer in it.The jth small triangle of ith floor has an integer f(i,j), f(i,j) can be calculated by such rules:

· f(i,1)=f(i,2*i-1)=1 for all i [1,n]
· f(i,j)=f(i-1,j-1) if j is even for all i [1,n].
· f(i,j)=f(i,j-1)+f(i,j+1) if j is odd for all i [1,n].




Hery wants you to help him to caculate .

The first line is an integer T, the test cases.
For each test cases, input 2 integers n,m.

For each n,m, ouput  in one line.

4
1 1
2 1
3 1
3 3

1
1
1
2