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

1132. Квадратный корень

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

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

В первой строке находится одно число K — количество тестов (K ≤ 100000). Каждая следующая строка представляет собой отдельный тест, который содержит целые числа a и n (1 ≤ a, n ≤ 32767, n простое, a и n взаимно простые).

Результат

Для каждого теста программа должна вычислить все возможные значения root (a, n) в диапазоне от 1 до n − 1 и вывести их в возрастающем порядке в одной строке, разделяя одним пробелом. Если для текущего теста корней не существует, программа должна вывести в отдельной строке сообщение ‘No root’.

Пример

исходные данныерезультат
5
4 17
3 7
2 7
14 31
10007 20011
2 15
No root
3 4
13 18
5382 14629
Автор задачи: Михаил Медведев