You are given two integers $$$a$$$ and $$$b$$$. In one turn, you can do one of the following operations:

Take an integer $$$c$$$ ($$$c \gt 1$$$ and $$$a$$$ should be divisible by $$$c$$$) and replace $$$a$$$ with $$$\frac{a}{c}$$$;
Take an integer $$$c$$$ ($$$c \gt 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:

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.

Another Problem About Dividing Numbers