Проблема 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.