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 Format :

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

Output Format :

Print in a each output line Case no. 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 <= 10^9

1 <= m <= 10^8

Sample Input :

2

6 5

100 45

Sample 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 no. of proper divisors of 1 is a Fibonacci number.