WBILL - Water Bill Company


Recently, clean water has became scarce and expensive. Louis water company, the one and only water company in your country, has raised the rates for water supply. The table below shows the new rates (consumption is always a positive integer):

Range
(Liters)
Price
(Rapiuhs)
1-100 2
101-1000 3
1001-10000 5
10001-1000000 7
>1000000 11

This means that, when calculating the amount to pay, the first 100 liters have a price of 2 Rapiuhs each; the next 900 liters (between 101 and 1000) have a price of 3 Rapiuhs each and so on. For instance, if you consume 10987 liters you will have to pay 2*100 + 3*900 + 5*9000 + 7*987= 54809 Rapiuhs.

Many people were unhappy with the new rates. After that, Malfple, the infamous hacker in your country, hacked the company server and modified the billing system. Instead of showing the bill of each customers, the billing system now shows the price for the sum of the usage of every 2 customers and the absolute difference between the billing of the 2 customers. As a noted programmer there, the company asks you to help them to create a program to determine the amount billing of each costumer, given the value from the hacked billing system.

Input

Input starts with an integer T (1 ≤ T ≤ 1000), denoting the number of test cases. Each of the test case consists of integer N and M (0 ≤ M ≤ N ≤ 2*10^9), denoting the the price for the sum of the usage of every 2 customers and the absolute difference of billing between two customers. You can assume there is always a unique solution, that is, there exists exactly one pair of consumption that produces those numbers.

Output

For each case, print "Case #X: A B", where X (1 ≤ X ≤ T) is the case number, A and B are the amount of the 2 customers have to pay in increasing order. There must be no trailing spaces at the end of printed lines, neither empty characters. Print a newline after each testcase.

Example

Input:
3
200 100
2240 1955
21350 20466

Output:
Case #1: 50 150
Case #2: 114 2069
Case #3: 269 20735

hide comments
nadstratosfer: 2018-11-17 23:51:27

Harder than I expected. Could be a classical unless there is a simple solution that evaded me.

Malfple: 2016-11-30 10:24:51

why me..
Re : Hi :p

Last edit: 2016-12-15 10:22:15
hanstan: 2016-11-25 15:35:16

When a problem created by a high schooler is used as a task for undergraduates...
Good luck all :p


Added by:hanstan
Date:2016-06-17
Time limit:0.200s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:Self