Атака на 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.

Приклади