Проблема RSA полягає в наступному: дано натуральне число \textbf{n}, яке є добутком двох різних простих непарних чисел \textbf{p} та \textbf{q}, натуральне \textbf{e} таке що \textbf{НСД(e, (p−1)·(q−1)) = 1}, а також ціле \textbf{c}. Необхідно знайти таке натуральне \textbf{m}, що \textbf{m^e = c (mod n)}. \InputFile Перший рядок містить кількість тестів \textbf{k} (\textbf{k} ≤ \textbf{2000}). Кожний наступний рядок є окремим тестом і містить три числа \textbf{e}, \textbf{n} та \textbf{c} (\textbf{e}, \textbf{n}, \textbf{c} ≤ \textbf{32000}, \textbf{n = p · q}; \textbf{p}, \textbf{q} --- різні непарні прості числа, \textbf{НСД(e, (p−1)·(q−1)) = 1}, \textbf{e} < \textbf{(p − 1)·(q − 1))}. \OutputFile Для кожного тесту в окремому рядку надрукувати значення \textbf{m}.