PUCMMT02 - Square-Free Product (Hard)

no tags 

Integer X is Square-Free if and only if p2 (p is prime) does not divide it. For example, 15 is a square-free number but 12 isn't, because 22 = 4 is one of its divisors.

 

Write a program that outputs whether the product of two numbers is a square-free number.

 

Input

 

The first line contains T (1 ≤ T ≤ 100), the number of test cases. T lines follow, one per test case. Each of these lines contain two integers a and b (1 ≤ a, b ≤ 1018). a and b are NOT necessarily square-free.

 

Output

 

Per test case:

 

  • Output a single line containing "YES" if the product of a and b is square-free, or "NO" otherwise. In any case, do not include quotes in your output.

 

Sample cases

 

Input

4

1 1

6 13

10 2

12 1

Output

YES

YES

NO

NO


hide comments
Alexey Malistov: 2016-10-15 21:59:21

I believe that some tests are wrong. There is a pair "a" and "b" (I know this pair) where my accepted (by SPOJ) code prints wrong result. But if I correct my code then SPOJ does not accept it.

Sergio Vieri: 2015-10-21 15:10:51

AC 0.46s 2.9M using Assembly... (806 lines, 12758bytes)

Last edit: 2015-10-21 15:14:21
Min_25: 2015-10-18 05:06:17

Incorrect constraints: a or b can be larger than 10^18.

Last edit: 2015-10-18 05:39:40

Added by:kojak_
Date:2014-09-05
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU
Resource:PUCMM Team Selection Contest #4