D. Еще одна задача про деление чисел
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам даны два целых числа $$$a$$$ и $$$b$$$. За один ход вы можете выполнить одно из следующих действий:

  • Взять целое число $$$c$$$ ($$$c > 1$$$, $$$a$$$ делится на $$$c$$$) и заменить $$$a$$$ на $$$\frac{a}{c}$$$;
  • Взять целое число $$$c$$$ ($$$c > 1$$$, $$$b$$$ делится на $$$c$$$) и заменить $$$b$$$ на $$$\frac{b}{c}$$$.

Ваша цель сделать $$$a$$$ равным $$$b$$$, используя $$$k$$$ этих операций.

Например, числа $$$a=36$$$ и $$$b=48$$$ можно сделать равными за $$$4$$$ хода:

  • $$$c=6$$$, делим $$$b$$$ на $$$c$$$ $$$\Rightarrow$$$ $$$a=36$$$, $$$b=8$$$;
  • $$$c=2$$$, делим $$$a$$$ на $$$c$$$ $$$\Rightarrow$$$ $$$a=18$$$, $$$b=8$$$;
  • $$$c=9$$$, делим $$$a$$$ на $$$c$$$ $$$\Rightarrow$$$ $$$a=2$$$, $$$b=8$$$;
  • $$$c=4$$$, делим $$$b$$$ на $$$c$$$ $$$\Rightarrow$$$ $$$a=2$$$, $$$b=2$$$.

Для заданных чисел $$$a$$$ и $$$b$$$ определите, можно ли сделать их равными ровно за $$$k$$$ ходов.

Входные данные

В первой строке содержится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$). Далее следуют $$$t$$$ наборов входных данных.

Каждый набор входных данных характеризуется тремя целыми числами $$$a$$$, $$$b$$$ и $$$k$$$ ($$$1 \le a, b, k \le 10^9$$$).

Выходные данные

Для каждого набора входных данных выведите:

  • «Yes», если можно ли сделать числа $$$a$$$ и $$$b$$$ равными ровно за $$$k$$$ ходов;
  • «No», иначе.

Строки «Yes» и «No» можно выводить в произвольном регистре.

Пример
Входные данные
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