This Can't Go On Forever

Problem

Long ago, in a galaxy far, far away, there was a world whose favorite pet — the taye — reproduced by budding. Once a young taye separated from its parent, it needed exactly one unit of time to mature, which is also exactly how long a fresh bud takes to grow and separate from its parent. Tayes live practically forever, so their owners like to count how many they will eventually have. Suppose that at time $0$ you own no taye, and at time $1$ a friend gives you a single freshly budded (still immature) taye.

The number of tayes you own then follows the recurrence

$$T(0) = 0, \quad T(1) = 1, \quad T(n) = T(n-1) + T(n-2) \ \text{for } n > 1.$$

These are the Fibonacci numbers. If the recurrence is computed under a fixed modulus $m$ (every value taken modulo $m$), the sequence of remainders eventually starts repeating. The question is: how long is one full period before it repeats?

The first few sequences look like this:

Modulus	Start of the sequence under that modulus	Period length
2	0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1	3
3	0 1 1 2 0 2 2 1 0 1 1 2 0 2 2 1 0 1 1 2 0 2 2	8
4	0 1 1 2 3 1 0 1 1 2 3 1 0 1 1 2 3 1 0 1 1 2 3	6
5	0 1 1 2 3 0 3 3 1 4 0 4 4 3 2 0 2 2 4 1 0 1 1	20

For each modulus given in the input, determine the length of the smallest period of this sequence and report it.

Input

The input contains an unknown number of lines. Each line holds a single integer $m$ with $2 \le m \le 16777216$ (that is, $2^{24}$). The final line contains $0$, which marks the end of the input and must not be processed.

Output

For each modulus $m$ in the input, print the modulus, a single space, and then the length of the smallest period of the Fibonacci sequence taken modulo $m$.