给你两个整数 $$$a$$$ 和 $$$b$$$。在一轮中,您可以执行以下操作之一:
- 取一个整数 $$$c$$$ ($$$c > 1$$$ 且 $$$a$$$ 应能被 $$$c$$$ 整除)并将 $$$a$$$ 替换为 $$$\frac{a}{c}$$$;
- 取一个整数 $$$c$$$($$$c > 1$$$ 且 $$$b$$$ 应能被 $$$c$$$ 整除)并将 $$$b$$$ 替换为 $$$\frac{b}{c}$$$。
您的目标是使用 $$$k$$$ 回合使 $$$a$$$ 等于 $$$b$$$。
例如,在 $$$4$$$ 移动中,数字 $$$a=36$$$ 和 $$$b=48$$$ 可以相等:
- $$$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$$$ 轮数使它们相等。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$)。然后是 $$$t$$$ 测试用例。
每个测试用例包含三个整数 $$$a$$$、$$$b$$$ 和 $$$k$$$ ($$$1 \le a, b, k \le 10^9$$$)。
输出
对于每个测试用例输出:
- “是”,如果可以使数字 $$$a$$$ 和 $$$b$$$ 在 $$$k$$$ 轮次中完全相同;
- 否则“否”。
任何情况下都可以输出字符串“Yes”和“No”。
示例
输入 #1
8 36 48 2 36 48 3 36 48 4 2 8 1 2 8 2 1000000000 1000000000 1000000000 1 2 1 2 2 1
输出 #1
YES YES YES YES YES NO YES NO