RSA hücumu

RSA probleminin mahiyyəti belədir: verilmiş təbii ədəd n, hansı ki, iki fərqli sadə tək ədədin p və q hasilidir, təbii e elə ki, ƏBOB(e, (p−1)·(q−1)) = 1, həmçinin tam c. Elə təbii m tapmaq lazımdır ki, m^e = c (mod n).

Giriş verilənləri

Birinci sətir testlərin sayını k (k ≤ 2000) ehtiva edir. Hər bir növbəti sətir ayrı bir testdir və üç ədəd e, n və c (e, n, c ≤ 32000, n = p · q; p, q — fərqli tək sadə ədədlər, ƏBOB(e, (p−1)·(q−1)) = 1, e < (p − 1)·(q − 1)) ehtiva edir.

Çıxış verilənləri

Hər bir test üçün ayrı sətirdə m qiymətini çap edin.

Nümunələr