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

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

Ограничение времени: 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