eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

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

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

Ліміт часу 1 секунда
Ліміт використання пам'яті 256 MiB

Число x называется квадратным корнем числа a по модулю n тогда и только тогда, когда x^2 = a (mod n). Напишите программу, которая находит все квадратные корни числа a по модулю n.

Вхідні дані

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

Вихідні дані

Для каждого теста выведите все квадратные корни a в диапазоне [0, n-1] в возрастающем порядке в одной строке, разделяя одним пробелом. Если для текущего теста корней не существует, выведите в отдельной строке сообщение "No root".

Приклад

Вхідні дані #1
4
1 7
2 7
3 7
4 7
Вихідні дані #1
1 6
3 4
No root
2 5
Джерело III Міжнародна Літня школа програмування 2012 м. Севастополь