Manish like to play with bits, so he was recently gifted with a puzzle book on bits arithmetic by one of his friend on his birthday.

Manish couldn't solve any of the puzzles from the book and needs your help to solve one.
Given two integers m & n .Find the number of combinations of bit-size 'n' in which there are no 'm' consecutive '1'.

Input

The first line of the input contains an integer T denoting the number of test cases.

Each test consist of single line containing two integers m and n.

Output

For each test case, output a single line containing an integer corresponding to the
number of combinations of bit size n in which no m consecutive 1's occur.

Constraints

1 ≤ T ≤ 50

1 ≤ n ≤ 50

2 ≤ m ≤ 10

SAMPLE INPUT
1
2 3

SAMPLE OUTPUT
5

Explanation

The 3-bit combinations which satisfy our problem statement are 000 001 010 100 101.

见题面

见题面