CHKL - Distributing Chocolates

Ohani’s uncle has just returned from USA and brought a lot of chocolates for her. Ohani is very excited about it and wants to distribute the chocolates among her friends. But she is in a great problem. How she will distribute chocolates? Then suddenly an idea came in her mind.

Ohani loves lucky numbers a lot. She always thinks N is a lucky number for her. She wants to give chocolates to her friends according to the proper divisors of N. For this reason she needs chocolates as much as the sum of divisors of N. For example: If Ohani’s lucky number is 12, then it’s proper divisors are 1, 2, 3, 4 and 6. So, she need at most (1+2+3+4+6) = 16 chocolates. Now, if Ohani has 3 friends, then she can distribute chocolates them as below:

Give 1st friend 2 chocolates, 2nd friend 3 and 3rd friend 4 chocolates

Give 1st friend 2 chocolates, 2nd friend 4 and 3rd friend 6 chocolates and so on.

But Ohani don’t have much time to calculate at most how much chocolates she needs and again if she will be able to distribute chocolates between her M friends with her lucky number N.

(Note: A positive proper divisor is a positive divisor of a number N, excluding N itself)

Input

The first line of the input denotes the number of test cases T (T <= 1000000).

The next T lines describe each test case. Each test case contains two numbers, N (2<=N <= 1000000) & M (1<=M<=1000000) where N denotes Ohani’s lucky number and M denotes her number of friends.

Output

Each test case has one line of output. If it is impossible to distribute chocolates among M friends then just output:
Case X: Impossible

Here X is the test case number.

Otherwise, if it is possible to distribute, then first output a word “Yes” and then the number of chocolates Ohani at most needs to keep with her in the formate below:

Case X: Yes Y

Here, X is the test case number and Y is the number of chocolates.

Sample Input

Output for Sample Input

2
3 2
12 3

Case 1: Impossible
Case 2: Yes 16

 Problem Setter: Raihat Zaman Niloy, Jahangirnagar University

Alternative Solution: Md Abdul Alim, Dept. of Computer Science, Bangladesh University of Business & Technology


Added by:Alim
Date:2014-06-15
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

hide comments
2014-12-08 21:55:26 Francky
There's yet some DIVSUM problems on SPOJ main set, no need to set duplicates. There's no place in classical for such a task. Moved to tutorial.
@psetter : before put a problem in classical, try to search if the problem is yet present. Thanks for your comprehension.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.