Problem Description

wr recently learned the Euclidean algorithm to solve the greatest common divisor,then he realized that the algorithm can also be able to solve the least common multiple.In order to train the skill of code,he find a number p(1<=p<=2^25)and a number q(1<=q<=2^25) then he got n=p*q,he calculated a₁=∑gcd(i, n) 1<=i <=n and a₂= ∑lcm(i, n) 1<=i <=n,he wants to know if a2-a1 is the multiple of c(1<=c<=10^9)

Input

The first line contains the number of scenarios.
Every scenario consists of a single line containing two integers n and c separated by a space.

Output

for every scenario print a single line contain "yes" or "no"
if the difference is the multiple of c print "yes",otherwise print "no"

2
6 100
4 2

no
yes