In Schematics Country, there is a place called NPC Town. NPC Town has many restaurants, each with their own signature dishes. Of course, NPC Town becomes one of the most designated travel place for tourists. Joke is an adventurer that likes to try many kinds of food. One day, Joke wants to taste all food in NPC Town. Because Joke likes every restaurant's signature dish, time flies so fast that it's now the last day of Joke's visit to NPC Town. For his last visit, he decides to go to a restaurant that his friend recommended, the restaurant is called “SaAn” (Sate Andaru). SaAn serves satay with three types of meat: chicken, goat, and buffalo. The unique thing about SaAn is each Satay can contain multiple types of meat. Every customer can order a combination of satay. If SaAn can't fulfill the customer's order, then the customer don't have to pay.

Knowing that, of course Joke wants to eat for free. He conjures a set of condition that must be met for his satay:

• The first and last piece of each satay must be chicken meat.
• There can't be two consecutive goat meat pieces.
• There can't be two consecutive buffalo meat pieces.
• The maximum number of goat meat and buffalo meat in each satay is K.
• The number of meat in each satay is N.

The number of satay that Joke order is the number of possible combination of the above condition. Since the number of satay can be overwhelming, Joke decides that he will modulo the number of satay by 1000000007.

Since Andaru doesn't want to give free food, he asks for your help to count the number of satay that must be served to Joke.

Input

First line contains a T, number of test case.

Each test case is a line containing N and K.

Output

Number of satay that must be served to Joke.

Sample Input

2
2 1
4 3

Sample Output

1
7