Hyper Harmonic number#3210

Hyper Harmonic number

8 seconds
64 megabytes
Very easy

Harmonic numbers are almost the most harmonious. However, the ordinary harmonic series does not show the same beauty and simplicity as the sequence invented by the rabbit Brian. Define the -th harmonic number as follows:

Brian believes that such a harmonic number is still not the most harmonious. He believes that there is a hyper harmonic number, and defines it as:

= H_1 \cdot H_2 \cdot H_3 \cdot ... \cdot H_k,

i.e.

Brian believes that the number will become even more harmonic if it is calculated modulo , where is a prime number.

While investigating hyper harmonic numbers, Brian noticed that starting from some k_z, all subsequent hyper harmonic numbers are equal to zero (calculated modulo ). Brian called the number k_z the hyper harmonic dimension of .

Formally, k_z is such that for all 1 \leq k < k_z, the hyper harmonic number is not modulo , and for k_z \leq k \leq n - 1, it is modulo (all calculations are done modulo ).

Find the hyper harmonic dimension for the given prime .

Input

The first line contains one integer (1 \leq T \leq 100) — the number of tests. Each of the following lines contains one integer (2 \leq n \leq 10^6). It is guaranteed that is a prime number.

Output

For each test, output the hyper harmonic dimension in a separate line.

Examples

Example 1

Loading
Loading