Гармонические числа почти самые гармонические. Но обычный гармонический ряд не демонстрирует той красоты и простоты, который покахывает ряд, придуманный криликом Брайаном. Определим \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 Для каждого теста выведите единственное число в отдельной строке -- размерность гипергармоничности.