Атака на RSA#1561
Проблема RSA полягає в наступному: дано натуральне число , яке є добутком двох різних простих непарних чисел та , натуральне таке, що \text{НСД}(e, (p-1)\cdot(q-1)) = 1, а також ціле . Необхідно знайти таке натуральне , що m^e \equiv c \pmod{n}.
Перший рядок містить кількість тестів (k \leq 2000). Кожний наступний рядок є окремим тестом і містить три числа , та (e, n, c \leq 32000, n = p \cdot q; , — різні непарні прості числа, \text{НСД}(e, (p-1)\cdot(q-1)) = 1, e < (p-1)\cdot(q-1)).
Для кожного тесту в окремому рядку надрукувати значення .
Приклад 1