VPL0_C - Collision on Christmas Eve

no tags 

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: A0=1, A1=A0+K+1, A2=A1+K+2, and so on. The value of An 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

hide comments
AMAN MISHRA: 2014-10-18 16:34:18

what is subtask and the constraints given in the end??

Miguel Oliveira: 2013-09-12 23:29:09

are you exploiting the input to get to 0.00 ?

(Tjandra Satria Gunawan)(曾毅昆): 2013-01-03 12:22:30

@Ehor Nechiporenko: Haha, congratulations finally you know the secret.. There's also the similar secret behind my solution in Saving BOB problem ;-)

Ehor Nechiporenko: 2013-01-03 11:20:51

Realy nice.
@Tjandra, I know your solution ;-))

Ehor Nechiporenko: 2012-12-21 08:22:45

@Daniel, actually it doesn't matter when you will print the answer after the first or after last test, because stdin and stdout in SPOJ do not intersect

Daniel Connolly: 2012-12-20 02:35:44

Just to confirm, we should output the answer after each input and not after all test-cases are entered? I get WA but correct for all the test-cases provided.

(Tjandra Satria Gunawan)(曾毅昆): 2012-12-11 02:09:10

and finally AC in 0.00s ;-)

(Tjandra Satria Gunawan)(曾毅昆): 2012-12-11 02:09:10

My full tricky brute-force code without any precomputation got AC :-P


Added by:Venezuelan Programming League
Date:2012-12-08
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own problem used for VPL0-Contest