CF1538D.Another Problem About Dividing Numbers

You are given two integers $a$ and $b$ . In one turn, you can do one of the following operations:

• Take an integer $c$ ( $c > 1$ and $a$ should be divisible by $c$ ) and replace $a$ with $\frac{a}{c}$ ;
• Take an integer $c$ ( $c > 1$ and $b$ should be divisible by $c$ ) and replace $b$ with $\frac{b}{c}$ .

Your goal is to make $a$ equal to $b$ using exactly $k$ turns.

For example, the numbers $a=36$ and $b=48$ can be made equal in $4$ moves:

• $c=6$ , divide $b$ by $c$ $\Rightarrow$ $a=36$ , $b=8$ ;
• $c=2$ , divide $a$ by $c$ $\Rightarrow$ $a=18$ , $b=8$ ;
• $c=9$ , divide $a$ by $c$ $\Rightarrow$ $a=2$ , $b=8$ ;
• $c=4$ , divide $b$ by $c$ $\Rightarrow$ $a=2$ , $b=2$ .

For the given numbers $a$ and $b$ , determine whether it is possible to make them equal using exactly $k$ turns.

The first line contains one integer $t$ ( $1 \le t \le 10^4$ ). Then $t$ test cases follow.

Each test case is contains three integers $a$ , $b$ and $k$ ( $1 \le a, b, k \le 10^9$ ).

For each test case output:

• "Yes", if it is possible to make the numbers $a$ and $b$ equal in exactly $k$ turns;
• "No" otherwise.

The strings "Yes" and "No" can be output in any case.