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.
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 the only number in a separate line for each test – the Hyper Harmonic Dimension.