Hyper Harmonic number
Hyper Harmonic number
Harmonic numbers almost the most harmonious. However, the usual harmonic series does not demonstrate such beauty and simplicity, as the row, invented by the rabbit Brian. Let's define the n-harmonic number as follows:
Brian believes that such a harmonic number is still not the most harmonious. He believes that there is Hyper Harmonic number, and defines it as follows:
= H_1·H_2·H_3·...·H_k,
i.e.
Brian believes that the number will become even more harmonic, if calculate it by module n. The number n is a prime.
Brian noticed that starting from some k_z all the following Hyper Harmonic numbers are equal to zero (by module n). He named the number k_z as Hyper Harmonic Dimension of the number n.
Formally speaking, k_z – is such a number, so for all 1 ≤ k < k_z : ≠0, and for k_z ≤ k ≤ n−1: =0 (all calculations are by module n).
Find for the given prime integer n its Hyper Harmonic Dimension.
Input data
The first line of input contains the only number T (1 ≤ T ≤ 100) – the number of tests. Each of the following T lines contains the only integer n (2 ≤ n ≤ 10^6). It’s guaranteed that n is a prime number.
Output data
Output the only number in a separate line for each test – the Hyper Harmonic Dimension.
Examples
3 2 3 5
2 2 4