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 .
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.
For each test, output the hyper harmonic dimension in a separate line.
Example 1