A. Divide and Conquer

time limit per test: 1 second

memory limit per test: 256 megabytes

input: standard input

output: standard output

You are given two positive integers xx and yy.

You are allowed to perform the following operation any number of times (possibly zero):

• Choose any positive integer zz such that zz divides xx;
• Set x:=xzx := \frac{x}{z}.

Determine whether you can make xx exactly equal to yy using this operation.

Input

The first line of the input contains a single integer tt (1≤t≤1041 \le t \le 10^4) — the number of test cases. The description of each test case follows.

The only line of each test case contains two space-separated integers and ($$).

Output

For each test case, print "YES" if you can make exactly equal to and "NO" otherwise.

You can output "YES" and "NO" in any case (for example, strings "yEs", "yes" and "Yes" will be recognized as a positive response).

Example

Input

3

12 2

6 7

99 79

Output

YES

NO

NO

Note

For the first test case,

• Choosing makes
• Choosing makes

For the second test case, it can be shown that it is impossible to make equal to .