Problem E: Balanced parantheses

How many balanced sequences of 2n parantheses ( ) have at most k consecutive equal characters ?

A sequence of parantheses is balanced if open and closed parantheses are matched one-to-one, with each closed paranthesis after the matching open one.

Input: a line with the number T of tests, followed by T lines, each with two natural numbers n and k.

Output: T lines, each with the corresponding result.

Example: Input

Output

Inputs and result t in 64 bits. Time: 1s

2

 

2

 

2

2

1

 

3

1