N nodes are labelled with integers from 1 to N. Now these N nodes are inserted in a empty binary search tree. But the constraint is that we have to build this tree such that height of tree is exactly equal to H. Your task is to find how many distinct binary search trees exists of these nodes such that their height is exactly equal to H ?

Two BSTs are considered to be different if there exist a node whose parent is different in both trees.

Input

Input First line contains 1<=T<=10 the number of test cases. Following T lines contains 2 integers each. N and H. 1<=N<=500, 0<=H<=500.

Output

For each test case print the required answer modulo 1000000007.

Example

Input:
1
2 1
Output:
2