Функция Эйлера 1
(Время: 0,5 сек. Память: 32 Мб Сложность: 47%)
Функция Эйлера ϕ(N) – мультипликативная арифметическая функция, значение которой равно количеству натуральных чисел, меньших либо равных N и взаимно простых с ним. По сути, это количество натуральных чисел в отрезке [1, N], наибольший общий делитель которых с N равен единице. Например, ϕ(14) = 6.
Рассмотрим такие N, для которых ϕ(N) является перестановкой цифр N. Например, ϕ(21) = 12, ϕ(4435) = 3544.
Вам необходимо ответить на Q запросов, Для каждого заданного qi вам нужно вывести на одной строке значение N, для которого 1 < N < qi, ϕ(N) является перестановкой N, а отношение N/ϕ(N) дает минимум. В случае нескольких вариантов ответа, выведите наибольший, в противном случае выведите «-1» без кавычек.
Входные данные
В первой строке входного файла INPUT.TXT находится натуральное число Q – количество запросов (1 ≤ Q ≤ 105).
Во второй строке через пробел даны Q натуральных чисел qi (1 < qi ≤ 108).
Выходные данные
В выходной файл OUTPUT.TXT выведите ответ на задачу.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 3
50 100 1000 | 21 63 291 |
Автор задачи
Владимир Игоревич Лукьянчиков
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
