ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Соревнование команд УрГУ. Март 2002

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

E. Идемпотенты

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Число x называется идемпотентом по модулю n, если
x*x = x (mod n)
Напишите программу, которая найдёт все идемпотенты по модулю n, где n является произведением двух различных простых чисел p и q.

Исходные данные

Первая строка содержит количество тестов k (1 ≤ k ≤ 1000). Каждая из следующих k строк содержит одно число n < 109.

Результат

Выведите в i-й строке все идемпотенты i-го теста в порядке возрастания. Печатать нужно только неотрицательные решения, меньшие n.

Пример

исходные данныерезультат
3
6
15
910186311
0 1 3 4
0 1 6 10
0 1 303395437 606790875
Автор задачи: Павел Атнашев
Источник задачи: Соревнование команд УрГУ, март 2002
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1204. Идемпотенты