Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. Another Problem About Dividing Numbers

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou 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.

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.

Example

Input

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

Output

YES YES YES YES YES NO YES NO

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/12/2021 14:19:04 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|