For a given positive integer $n$, we consider whether it can be represented as the product of $k$ distinct positive integers.

Input

The first line of input contains a single integer $t$ ($1 \le t \le 4\,000$), representing the number of test cases to consider. Each of the next $t$ lines contains two integers $n_{i}$ and $k_{i}$ ($1 \le n_{i} \le 10^{9}$, $1 \le k_{i} \le 20$).

Output

Your program should output exactly $t$ lines. The $i$-th line should contain one word YES or NO, depending on whether the number $n_{i}$ can be represented as the product of $k_{i}$ distinct factors.

Examples

Input 1

3
15 2
24 4
24 5

Output 1

YES
YES
NO