K-Perfect Pair

You are given an integer q denoting the number of queries. In each query, you are given three positive integers k, a, and b. Your task is to determine whether the pair (a, b) is k-perfect.

A pair (a, b) is defined to be k-perfect if and only if the product of a and b is a perfect k^th power. In other words, there must exist an integer x such that

$$ x^{k} = a \times b. $$

For each query, output YES if such an integer x exists, and NO otherwise.

inputFormat

The first line contains an integer q (1 ≤ q). Each of the next q lines contains three space-separated integers: k, a, and b, where 1 ≤ k, a, b ≤ 10⁹.

outputFormat

For each query, print a single line containing YES if a × b is a perfect k^th power, and NO otherwise.

sample

3
2 4 9
3 2 16
1 7 8

YES
NO
YES