Гармонійні числа майже найгармонійніші. Проте звичайний гармонійний ряд не демонструє такої краси і простоти, як ряд, придуманий кріликом Брайаном. Визначимо \textbf{n}-те гармонійне число так: \includegraphics{https://static.e-olymp.com/content/6a/6a8a529e6b8d7b4725989e078018ab59c31cf97a.jpg} Брайан вважає, що таке гармонійне число все ж не найгармонійніше. Він вірить, що існує гіпергармонійне число, і визначив його так: \includegraphics{https://static.e-olymp.com/content/b9/b98e03df789543312e3a417f8356dc25cf952a37.jpg} = \textbf{H_1·H_2·H_3·...·H_k}, тобто \includegraphics{https://static.e-olymp.com/content/cf/cf95ddd810c5297ad58e2c1dd1ecb3683a0c093e.jpg} Брайан вірить, що число стане ще гармонічнішим, якщо обчислити його за модулем \textbf{n}. Оскільки задачка проста, то й число \textbf{n} буде простим. Досліджуючи гіпергармонійні числа, Брайан зауважив, що починаючи з деякого \textbf{k_z} усі наступні гіпергармонійні числа рівні нулю (обчислені за модулем \textbf{n}). Число \textbf{k_z} Брайан назвав розмірністю гіпергармонійності числа \textbf{n}. \includegraphics{https://static.e-olymp.com/content/b9/b98e03df789543312e3a417f8356dc25cf952a37.jpg} \includegraphics{https://static.e-olymp.com/content/b9/b98e03df789543312e3a417f8356dc25cf952a37.jpg} Формально, \textbf{k_z} --це таке число, що для усіх \textbf{1} ≤ \textbf{k }< \textbf{k_z} : ≠\textbf{0}, а для \textbf{k_z} ≤ \textbf{k} ≤ \textbf{n−1}: =\textbf{0} (усі обчислення за модулем \textbf{n}). Знайдіть для заданого простого \textbf{n} розмірність гіпергармонійності. \InputFile Перший рядок містить єдине ціле число \textbf{T} (\textbf{1} ≤ \textbf{T} ≤ \textbf{100}) -- кількість тестів. Для кожного тесту в окремому рядку записане одне ціле число \textbf{n} (\textbf{2} ≤ \textbf{n} ≤ \textbf{10^6}) . Гарантується, що \textbf{n} -- просте. \OutputFile Для кожного тесту виведіть єдине число в окремому рядку -- розмірність гіпергармонійності.