题目描述

33DAI 和 Tom 各有一个正整数，分别是 $a$ 和 $b$。

每次操作，33DAI 可以任选其中一个数，把它除以一个大于 $1$ 的因子（必须整除，结果仍是正整数）。

例如，$12$ 可以除以 $2, 3, 4, 6, 12$，变成 $6, 4, 3, 2, 1$；而 $7$ 只能除以 $7$，变成 $1$。

33DAI 想知道：能否恰好进行 $k$ 次操作，使得两个数相等？

输入格式

第一行一个整数 $T$，表示测试用例组数。

接下来 $T$ 行，每行三个整数 $a, b, k$（$1 \le a, b \le 10^9$，$0 \le k \le 10^9$）。

输出格式

对每组测试用例输出一行：如果能够恰好 $k$ 次操作后相等，输出 YES，否则输出 NO。

5
1 1 0
1 1 1
4 2 2
6 10 1
6 10 3

YES
NO
YES
NO
YES

样例 1 解释

• 第 $1$ 组：两个数已经相等，做 $0$ 次操作即可。
• 第 $2$ 组：不存在恰好 $1$ 次操作后相等的方案。
• 第 $3$ 组：$4 \div 4 = 1$，$2 \div 2 = 1$，两次操作后都变成 $1$。
• 第 $4$ 组：不存在恰好 $1$ 次操作后相等的方案。
• 第 $5$ 组：$6 \div 3 = 2$，$2 \div 2 = 1$，$10 \div 10 = 1$，三次操作后都变成 $1$。

3
1000000000 1000000000 36
2 3 2
12 18 1

YES
YES
NO

样例 2 解释

• 第 $1$ 组：$10^9 = 2^9 \times 5^9$，两边各自用 $9 + 9 = 18$ 次除法变成 $1$，一共 $36$ 次。
• 第 $2$ 组：$2 \div 2 = 1$，$3 \div 3 = 1$，两次操作后都变成 $1$。
• 第 $3$ 组：不存在恰好 $1$ 次操作后相等的方案。

样例 3

见 divide3.in 与 divide3.ans。

样例 4

见 divide4.in 与 divide4.ans。

数据范围

对于全部测试数据，保证：

• $1 \le T \le 10^4$；
• $1 \le a, b \le 10^9$；
• $0 \le k \le 10^9$。

子任务

本题共 20 个测试点，按测试点计分：

每个测试点单独评分，全部测试点的得分之和即为本题得分。