Ram loves those numbers which are square of any number. To check his love for these numbers one day Sham gives him two numbers a and p where p is prime number and asks him if it is possible to find any square number which gives modulo a when divided by p. This task is difficult for Ram so he asks for your help. Help Ram to find whether such number exists or not.

INPUT

First line contains number of test cases T. Eash test case contains two numbers a and a prime number p.

OUTPUT

Print "YES" if any n exists such that (n*n)%p=a else print "NO"(without quotes).
NOTE : n must be greater than 0.

Constraints

1<=T<=1000
1<=a<=1000000
3<=p<=1000000 (p is prime number)