Вам дано натуральне число \(N\). Відомо, що \(N\) можна представити як \(N=p^2 q\) за допомогою двох різних простих чисел \(p\) і \(q\).

Знайдіть \(p\) і \(q\).

Вам потрібно розв’язати \(Т\) тестових випадків.

Обмеження

• Усі значення у вхідних даних є цілими числами.
• \(1≤T≤10\)
• \(1≤N≤9×10^{18}\)
• \(N\) можна представити як \(N=p^2 q\) за допомогою двох різних простих чисел \(p\) і \(q\).

Формат вхідних даних

Перший рядок містить ціле число \(T\) - кількість тестів.

Потім слідують \(T\) рядків, кожен рядок містить ціле число \(N\).

Формат вихідних даних

У вихідний потік виведіть Т рядків. \(i\)-й \((1≤i≤T)\) рядок має містити \(p\) і \(q\) для \(i\)-го тесту, розділених пробілом. За умов обмежень цієї задачі можна довести, що пара простих чисел \(p\) і \(q\), для яких \(N=p^2 q\), єдина.

Приклад вхідних даних

3
2023
63
1059872604593911

Приклад вихідних даних

17 7
3 7
104149 97711

Для першого тестового випадку ми маємо \(N=2023=17^2 ×7\). Отже, \(p=17\) і \(q=7\).