Equation Equals Hazards

Limits 1s, 512 MB

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 (T <= 1000), denoting the number of test cases. Each test case contains two integers A and M (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.

Sample

InputOutput
1
7 13
Yes

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

Submit

Login to submit.

Statistics

80% Solution Ratio
Shipon_diuEarliest, May '16
rayhan50001Fastest, 0.0s
prodip_bsmrstuLightest, 0 B
ptorbatiiShortest, 78B
Toph uses cookies. By continuing you agree to our Cookie Policy.