Петрик знайшов у книжці цікаве математичне рівняння: X^Y mod Z = K
Він швидко навчився знаючи X, Y та Z обчислювати K. Але тепер його зацікавило, як, знаючи X, Z та K, швидко обчислити Y. Допоможіть йому у цьому.
У першому рядку задано кількість прикладів T, які потрібно розв’язати Петрику (0 < T < 21), і у наступних T рядках по три числа через пропуск: X, Z, K (0 ≤ X, Z, K ≤ 10 ^9 ).
Для кожного прикладу виведіть у окремому рядку мінімально можливе Y (0 ≤ Y < Z), або у випадку відсутності розв’язку "No Solution".