Another Problem About Dividing Numbers

题意翻译

给定两个整数 $a, b$ 和一个操作数 $k$。对于每一次操作，你有如下两种选择： - 选择一个能整除 $a$ 的大于一的整数 $c$，用 $\dfrac{a}{c}$ 替换 $a$。 - 选择一个能整除 $b$ 的大于一的整数 $c$，用 $\dfrac{b}{c}$ 替换 $b$。 然后询问，是否存在一种操作方法，使得在**恰好** $k$ 次操作后，$a=b$。 数据范围：$1 < a, b, k < {10}^9$。

题目描述

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.

输入输出样例

输入样例 #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