B. Симон и торты успеха
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
When I succeed, we'll share the cakes together!
— SHUN

У Симона есть $$$n$$$ друзей и огромное количество тортов. Чтобы справедливо разделить торты, вам предлагается помочь ему решить следующую задачу:

  • Найдите минимальное целое положительное число $$$k$$$, такое что $$$n$$$ является делителем $$$k^n$$$.

Можно доказать, что ответ всегда существует при заданных ограничениях.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Единственная строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2\le n\le 10^9$$$) — количество друзей, которые есть у Симона.

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

Для каждого набора входных данных выведите одно целое число — минимальное $$$k$$$, которое вы нашли.

Пример
Входные данные
4
8
12
369
55635800
Выходные данные
2
6
123
2090
Примечание

В первом наборе входных данных:

  • $$$1^8=1$$$, и $$$8$$$ не является делителем $$$1$$$;
  • $$$2^8=256$$$, и $$$8$$$ является делителем $$$256$$$, потому что $$$256 = 8\cdot 32$$$.

Таким образом, минимально возможное $$$k$$$ равно $$$2$$$.

Во втором наборе входных данных $$$12$$$ является делителем $$$6^{12}=2\,176\,782\,336$$$, потому что $$$2\,176\,782\,336=12\cdot 181\,398\,528$$$.