Manku has still not learnt from KK's hard problem and continues bragging about himself. He claims that he can code problems even in his sleep. So one day Shark wakes him from sleep and asks him to solve a problem.

Shark gives him a number x and another number m and asks him to check whether any power of x is divisible by m. Now Manku is still sleepy and cannot solve the problem. Can you help him? If it is divisible then print "YES" (without quotes) else print "NO" (without quotes).

Input

First line contains number of test cases. Only line in each test case contains two numbers x and m.

Output

For each test case print "YES" or "NO".

Constraints

1<=x<=10^12 1<=m<=10^13