HDEVIL - Alia and Handsome Devil

no tags 

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.


hide comments
surajmall: 2016-12-23 17:31:05

simple good for beginners

Siddharth Singh: 2016-05-26 18:06:59

Brute Force+STL <3

dwij28: 2016-03-24 15:36:29

A very good adhoc / brute force problem.. :)

Akshit Johry: 2016-01-02 21:37:54

thanks scyth3r :)

ANIKET: 2015-08-02 13:03:56

@pranjuldb why my code is not getting accepted

:.Mohib.:: 2015-07-14 15:37:03

@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
vagesh_verma: 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
:.Mohib.:: 2015-07-14 15:07:06

AC in 0.00 :/ ..Constraints should be more tight....

scyth3r: 2015-07-14 13:52:30

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
Ankit Sultana: 2015-06-28 09:11:44

Watch out for the period in the output


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