Вам даны два целых числа \(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\) ходов.
Выходные данные
Для каждого набора входных данных выведите:
- «Yes», если можно ли сделать числа \(a\) и \(b\) равными ровно за \(k\) ходов;
- «No», иначе.
Строки «Yes» и «No» можно выводить в произвольном регистре.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|