Атака на RSA

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

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

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

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

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

Примеры