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

Атака на RSA

Атака на RSA

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Проблема RSA состоит в следующем: дано положительное целое число n, которое является произведением двух различных простых нечетных чисел p и q, положительное целое e, такое что НОД(e, (p - 1) · (q - 1)) = 1, а также целое c. Необходимо найти такое положительное целое m, что m^e = c (mod n).

Входные данные

Первая строка содержит количество тестов k (k2000). Каждая следующая строка является отдельным тестом и содержит три числа e, n и c (e, n, c32000, n = p · q; p, q - различные нечётные простые, НОД(e, (p - 1) · (q - 1)) = 1, e < (p - 1) · (q - 1)).

Выходные данные

Для каждого теста в отдельной строке вывести значение m.

Пример

Входные данные #1
3
9 187 129
11 221 56
7 391 204
Выходные данные #1
7
23
17