Equation Equals Hazards

You are given the equation, $GCD(A,M) = 1$. You have to determine whether there exists at least one integer $X$ such that $A \times X \space \texttt{mod} \space M = 1$.

Input

Input starts with an integer $T$ ($0 < T \le 1000$), denoting the number of test cases. Each test case contains two integers $A$ and $M$ ($1 \le A, M \le 1000000$).

Output

For each test case of input, print “Yes” if there exists at least one integer $X$ such that $A \times X \space \texttt{mod} \space M = 1$, print “No” otherwise.

Sample

1
7 13

Yes

This problem was authored for CodeMask Championship 2016 and is being hosted on Toph per organizer’s request.