# This Can’t Go On Forever

Time Limit: 2 Seconds Memory Limit: 65536 KB

“A long time ago in a galaxy far, far away…”, so long ago, in fact, that the Empire did not exist and there were planets without space travel. In a far corner was a world in which the predominant pet, called tayes, reproduced by budding. Once a taye had separated from its parent, it took one time unit to mature to the point of breeding, which, coincidentally, was the length of time for a new bud to grow and separate from its parent. The tayes are extremely long-lived, so that it became important to investigate how many someone might have, assuming that at time zero the person did not have a taye, and at time one had acquired an immature one, freshly budded from the mature taye belonging to a friend.

This ends up giving the following recurrence: T(0) = 0, T(1) = 1, T(n) = T(n–1) + T(n–2), for n > 1.

Computing at the time involved unsigned binary numbers with 24 bits. That motivated a particularly curious inhabitant, Leon, to investigate the series generated by that recurrence, but constrained by a modulus — and not just the modulo 224 forced by computing hardware. So the question becomes how long a series of number is generated by this recurrence, subject to arithmetic with a particular modulus, before it begins repeating. Here are the first few series:

The problem is to determine the length of the period for each modulus given in the input file and report it.

## Input

The input file contains an indeterminate number of lines, each containing a single integer *mod *guaranteed to be

in the range 2 ≤ mod ≤ 16777216 (2^{24}). The final line contains a 0 as end of data and should not be processed.

## Output

For each modulus in the input file, print the modulus, one blank, and then the size of the smallest period of these T numbers under that modulus.

## Sample Input

2 3 4 5 6 12345678 16777216 0

## Sample Output

2 3 3 8 4 6 5 20 6 24 12345678 700512 16777216 25165824Submit

Source: 2009 ACM-ICPC Pacific Northwest Region