Гіпергармонійні числа
Гармонійні числа майже найгармонійніші. Проте звичайний гармонійний ряд не демонструє такої краси і простоти, як ряд, придуманий кріликом Брайаном. Визначимо n-те гармонійне число так:
Брайан вважає, що таке гармонійне число все ж не найгармонійніше. Він вірить, що існує гіпергармонійне число, і визначив його так:
= H_1·H_2·H_3·...·H_k,
тобто
Брайан вірить, що число стане ще гармонічнішим, якщо обчислити його за модулем n. Оскільки задачка проста, то й число n буде простим.
Досліджуючи гіпергармонійні числа, Брайан зауважив, що починаючи з деякого k_z усі наступні гіпергармонійні числа рівні нулю (обчислені за модулем n). Число k_z Брайан назвав розмірністю гіпергармонійності числа n.
Формально, k_z –це таке число, що для усіх 1 ≤ k < k_z : ≠0, а для k_z ≤ k ≤ n−1: =0 (усі обчислення за модулем n).
Знайдіть для заданого простого n розмірність гіпергармонійності.
Вхідні дані
Перший рядок містить єдине ціле число T (1 ≤ T ≤ 100) – кількість тестів. Для кожного тесту в окремому рядку записане одне ціле число n (2 ≤ n ≤ 10^6) . Гарантується, що n – просте.
Вихідні дані
Для кожного тесту виведіть єдине число в окремому рядку – розмірність гіпергармонійності.