Beto, Dickie, Luis, Maxx, Charlie and Ricky like to play some wicked games in the summer. These games can easily be found in any social network. They like to play by drinking some strange liquid they call ”Aquameister” that can make you dizzy if you drink too much! Beto is tired of losing every time they play, but Charlie is the most capable to resist these games. That’s why Beto asked for your help! He wants to make Charlie feel dizzy before he does! The game consists on winning (clearly), and is given by a large row. He starts from position 1. For each row you must drink one small cup of Aquameister. If you repeat the same movement of dice he threw in his last turn, he drink again, for simplicity, we define the "same movement" with the same dice that Beto threw the last turn, by instance, if Beto threw (2, 1, 2), then Beto can throw (1, 2, 2), however, Beto may not throw the same (2, 1, 2), and so on for each roll. This goes on until Beto reach the position N. Being the last position, if Beto passes out, he lose the game and will drink twice and start again. However, for the sake of Beto, if he goes out he drinks twice and stops drinking.

Beto wants to know how many different ways he can end the game perfectly (that is arriving to the N position in the game) starting from the position 1. As this number can be very big, we ask you to output the answer modulo 1,000,000,007

Input

The first line contains an integer T, which specifies the number of test cases. Then, will follow the descriptions of T test cases.

Each case contains two integers N and D, being the size of the row and the number of dice you will throw per round (The dice are six-sided dice).

Output

For each input case you must print the string "Scenario #i:" where i is the case you are analyzing (starting from 1) then, the answer to the question described above.

Example

Input:
3
3 1
4 1
6 1

Output:
Scenario #1: 1
Scenario #2: 3
Scenario #3: 7

Constraints

Subtask 1 (10%)

• 1 ≤ T ≤ 50
• 1 ≤ N ≤ 5
• 1 ≤ D ≤ 2

Subtask 2 (30%)

• 1 ≤ T ≤ 100
• 1 ≤ N ≤ 100
• D = 1

Subtask 3 (60%)

• 1 ≤ T ≤ 50
• 1 ≤ N ≤ 100
• 1 ≤ D ≤ 3