Danny is preparing to receive his Christmas gift, their parents said that it is a very awesome gift and Danny could not think on anything else than what is inside the box.

Weeks ago, the parents of Danny gave him a homework that Danny didn’t complete because it was too boring for him, but suddenly, at December 25th, the parents are asking Danny to give the answer of his homework! Danny is falling into desperation and requires your help.

Now, before giving the Christmas gift, the parents asked Danny for the homework, and it goes like this: given two numbers N and K, find the number with the largest quantity of divisors following the progression: A₀=1, A₁=A₀+K+1, A₂=A₁+K+2, and so on. The value of A_n should not exceed the number N given.

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 only two numbers N and K, giving the maximum number to evaluate and the value of the progression’s constant.

The input must be read from standard input.

Output

For each input case you must print the string "Scenario #i: " where i is the test case you’re analyzing (starting by 1), followed by the number who contains the largest quantity of divisors in it with the number of divisors associated, in case of a tie, choose the smaller.

The output must be written to standard output.

Example

Input:
4
4 0
28 1
2 2
78 3
Output:
Scenario #1: 4 3
Scenario #2: 28 6
Scenario #3: 1 1
Scenario #4: 40 8

Subtask 1 - 20%

• 1 ≤ N ≤ 1,000
• 10 ≤ K ≤ 100

Subtask 2 - 30%

• 1 ≤ N ≤ 100,000
• 0 ≤ K ≤ 100

Subtask 3 - 50%

• 1 ≤ N ≤ 10,000,000
• 0 ≤ K ≤ 100