Since the annual fest is coming, rohit has decided to set up a lottery stall for the event. He makes several chits with a number written on it. The criteria for a number to be winning number is that the product of all the proper fractions with number as the denominator must be a fraction such that the numerator and denominator are relatively co-prime. Numerator can be very large so they should be modulo 110. Consider that more than one chit can be a winning chit. You have to help rohit in finding out that whether a chit is a winning chit or not.
Input: The first line of input will be an integer t denoting number of test cases. The next t lines will contain an integer n denoting the number on chit.
Output: The output must be of the form Case #: followed by either "YES" or "NO" denoting whether a chit is a winning chit or not.
Constraints: 1<T<=10^5
1<n<=10^12
For the first test case, product of (1/3)(2/3) gives 2/9. 2 mod 110 gives 2.Now 2 and 9 are co-primes. For the second test case, product of (1/4)(2/4)*(3/4) gives 6/64. 6 mod 110 gives 6. Now 6 and 64 are not co-primes.
