Maraqlı tənlik

Petrik kitabda maraqlı bir riyazi tənlik tapdı: X^Y mod Z = K

O, tez bir zamanda X, Y və Z bilmək şərti ilə K-nı hesablamağı öyrəndi. İndi isə onu maraqlandıran məsələ X, Z və K verilmiş halda Y-ni necə tez hesablamaqdır. Ona bu işdə kömək edin.

Giriş verilənləri

Birinci sətirdə Petriyin həll etməli olduğu nümunələrin sayı T verilir (0 < T < 21), və növbəti T sətirdə boşluqla ayrılmış üç ədəd: X, Z, K (0 ≤ X, Z, K ≤ 10^9).

Çıxış verilənləri

Hər bir nümunə üçün ayrıca sətirdə minimal mümkün Y (0 ≤ Y < Z) çıxarın, və ya həll olmadıqda "No Solution".

Nümunələr