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 \gt 1$ and $a$ should be divisible by $c$) and replace $a$ with $\frac{a}{c}$;
• Take an integer $c$ ($c \gt 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.

给你两个整数 $a$ 和 $b$。每轮操作中，你可以执行以下两种操作之一：

• 选取一个整数 $c$（满足 $c \gt 1$ 且 $a$ 能被 $c$ 整除），并将 $a$ 替换为 $\frac{a}{c}$；
• 选取一个整数 $c$（满足 $c \gt 1$ 且 $b$ 能被 $c$ 整除），并将 $b$ 替换为 $\frac{b}{c}$。

你的目标是恰好经过 $k$ 轮操作，使得 $a = b$。

例如，数字 $a=36$ 和 $b=48$ 可以在 $4$ 步内变得相等：

• 取 $c=6$，将 $b$ 除以 $c$ $\Rightarrow$ $a=36$, $b=8$；
• 取 $c=2$，将 $a$ 除以 $c$ $\Rightarrow$ $a=18$, $b=8$；
• 取 $c=9$，将 $a$ 除以 $c$ $\Rightarrow$ $a=2$, $b=8$；
• 取 $c=4$，将 $b$ 除以 $c$ $\Rightarrow$ $a=2$, $b=2$。

对于给定的 $a$ 和 $b$，判断是否可能恰好经过 $k$ 轮操作使它们相等。

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$).

第一行包含一个整数 $t$（$1 \le t \le 10^4$）。随后是 $t$ 个测试用例。

每个测试用例包含三个整数 $a$、$b$ 和 $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.

对于每个测试用例，输出：

• 若恰好经过 $k$ 步操作后能使数字 $a$ 和 $b$ 相等，则输出 "Yes"；
• 否则输出 "No"。

字符串 "Yes" 和 "No" 的大小写不限。