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 ≤ 10⁹

1 ≤ m ≤ 10⁸

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.