eolymp
bolt
Try our new interface for solving problems
Problems

Hyper Harmonic number

Hyper Harmonic number

Time limit 8 seconds
Memory limit 64 MiB

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 1k < k_z : ≠0, and for k_zkn−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 (1T100) – the number of tests. Each of the following T lines contains the only integer n (2n10^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

Input example #1
3
2
3
5
Output example #1
2
2
4
Source ACM-ICPC Ukraine 2012, 1st Stage Ukraine, April 21, 2012