Вам задано три цілі числа , та . Ви можете виконувати таку операцію:
Вибрати ціле число z>1 і помножити на , тобто x := x \cdot z
Визначте, чи можна зробити рівним , виконавши описану вище операцію рівно разів.
Перший рядок містить одне ціле число (1 \le t \le 500) кількість наборів вхідних даних.
Кожен набір вхідних даних містить три цілі числа , та (1 \le x,y \le 10^5 , 0 \le k \le 10^5).
Для кожного набору вхідних даних виведіть "YES" (без лапок), якщо можна зробити рівним рівно за операцій, і "NO" (без лапок) в іншому випадку.
Ви можете виводити відповідь у будь-якому регістрі (наприклад, рядки "yEs", "yes", "Yes" та "YeS" будуть розпізнані як ствердна відповідь).
Приклад 1
Підзадача ( балів): Без додаткових обмежень