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