codeforces#P1538D. Another Problem About Dividing Numbers

    ID: 32177 远端评测题 2000ms 256MiB 尝试: 1 已通过: 1 难度: 5 上传者: 标签>constructive algorithmsmathnumber theory*1700

Another Problem About Dividing Numbers

Description

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.

Input

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

Output

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.

Samples

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
YES
YES
YES
YES
YES
NO
YES
NO