G. Короткая задача
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Обозначим за $$$d(n)$$$ сумму всех делителей числа $$$n$$$, т.е. $$$d(n) = \sum\limits_{k | n} k$$$.

Например, $$$d(1) = 1$$$, $$$d(4) = 1+2+4=7$$$, $$$d(6) = 1+2+3+6=12$$$.

Для заданного числа $$$c$$$, найдите минимальное $$$n$$$ такое, что $$$d(n) = c$$$.

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

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

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

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

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

  • «-1», если не существует $$$n$$$, такого что $$$d(n) = c$$$;
  • $$$n$$$, иначе.
Пример
Входные данные
12
1
2
3
4
5
6
7
8
9
10
39
691
Выходные данные
1
-1
2
3
-1
5
4
7
-1
-1
18
-1