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
Akshat Mathur: 2015-06-03 22:21:25

Simple Brute Force :-)

ASHUTOSH DWIVEDI: 2015-05-17 11:10:31

easy one.......simple brute force
got 0.4points with it

Last edit: 2015-05-17 11:11:20
Harsh Rumalwala: 2014-12-28 23:41:29

Read the question properly...costed me a WA.and read note carefully.


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