Integer X is Square-Free if and only if p² (p is prime) does not divide it. For example, 15 is a square-free number but 12 isn't, because 2² = 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 ≤ 10¹⁸). 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

Input
4
1 1
6 13
10 2
12 1

Output
YES
YES
NO
NO