You are given the equation, GCD(A, M) = 1. You have to determine whether there exists at least one integer X such that A * X mod M = 1.

Input

Input starts with an integer T, denoting the number of test cases. Each test case contains two integers A and M.

Constraints

T <= 1000

1 <= A, M <= 1000000

Output

For each test case of input, print “Yes” if there exists at least one integer X such that A * X mod M = 1, print “No” otherwise.

Example

Input:
1
7 13

Output:
Yes

Problem Setter: Md Abdul Alim, Dept. of Computer Science, Bangladesh University of Business & Technology