EEH - 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 * 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


Added by:Alim
Date:2016-04-01
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:Own Problem

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.