HDEVIL - Alia and Handsome Devil

Alia has been assigned a homework by her maths teacher to find the "Handsome" numbers. She is confused about these numbers, as we all know that she is very "intelligent" :P

So she needs your help. Following is an exact line that her teacher has given about Handsome numbers : "Handsome number can be defined as a number such that sum of all the proper divisors of handsome number with modulus to m, has to be a devil number. This Devil number is a number whose total number of proper divisors, is a Fibonacci number (0, 1, 1, 2, 3, 5 ...)."

Note: Alia's lucky number is 1, so she assumes 1 as a proper divisor always :P

Input

First line of input is t (number of test cases) then next each t lines will contain two integers n (number that is to be checked), m.

Output

Print in a each output line Case number and "YES." if a number is a handsome number otherwise "NO.". (with a dot)

        Case_#i_:_YES.
        Case_#j_:_NO.

Here, '_' refers to a single space.

Constraints

t ≤ 100

2 ≤ n ≤ 109

1 ≤ m ≤ 108

Example

Input:
2
6 5
100 45

Output:
Case #1 : YES.
Case #2 : YES.

Explanation

Case #1 : proper divisors of 6 are 1, 2, 3 i.e. sum = 6 , taking mod with 5, i.e. 1. Now number of proper divisors of 1 is a Fibonacci number.


Added by:pranjuldb
Date:2014-09-09
Time limit:0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own problem from Codehurdle

hide comments
2016-12-23 17:31:05
simple good for beginners
2016-05-26 18:06:59 Siddharth Singh
Brute Force+STL <3
2016-03-24 15:36:29
A very good adhoc / brute force problem.. :)
2016-01-02 21:37:54 Akshit Johry
thanks scyth3r :)
2015-08-02 13:03:56 ANIKET
@pranjuldb why my code is not getting accepted
2015-07-14 15:37:03 :.Mohib.:
@vagesh you should use spoj toolkit link for this prob:
http://www.spojtoolkit.com/test/HDEVIL
I think you should try this one.
1
1 101

Last edit: 2015-07-14 16:15:23
2015-07-14 15:34:09
@mohib can u plz suggest me some good test cases i m getting wrong answers
edit: thanx...

Last edit: 2015-07-22 07:52:34
2015-07-14 15:07:06 :.Mohib.:
AC in 0.00 :/ ..Constraints should be more tight....
2015-07-14 13:52:30 scyth3r
pre-compute the Fibonacci numbers up to at most 15 terms.....
bcoz maximum value of Devil number will be 10^8-1 and total number of proper divisors for any number in range (1,10^8-1) will be less than 377, 15th Fibonacci number
Edit : For the given test cases simply compute up to 89!! :D:D

Last edit: 2015-07-14 13:57:08
2015-06-28 09:11:44 Ankit Sultana
Watch out for the period in the output
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.