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 starts with an integer T (T <= 1000), denoting the number of test cases. Each test case contains two integers A and M (1 <= A, M <= 1000000).
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.
1 7 13
This problem was authored for CodeMask Championship 2016 and is being hosted on Toph per organizer’s request.