Pseudo-Random Numbers

Computers normally cannot generate truly random numbers, but they are frequently used to generate sequences of pseudo-random numbers. These are produced by some algorithm, but for all practical purposes they appear to be truly random. Random numbers are used in many applications, including simulation.

A common pseudo-random number generation technique is the linear congruential method. If the last pseudo-random number generated was $L$, then the next number is generated by evaluating $(Z \times L + I) \bmod M$, where $Z$ is a constant multiplier, $I$ is a constant increment, and $M$ is a constant modulus.

For example, suppose $Z = 7$, $I = 5$, and $M = 12$. If the first random number (usually called the seed) is $4$, then the next few pseudo-random numbers are determined as follows:

Last Random Number, L | (Z×L+I) | Next Random Number, (Z×L+I) mod M
----------------------|---------|----------------------------------
         4            |   33    |                9
         9            |   68    |                8
         8            |   61    |                1
         1            |   12    |                0
         0            |    5    |                5
         5            |   40    |                4

As you can see, the sequence of pseudo-random numbers generated by this technique repeats after six numbers. It should be clear that the longest sequence that can be generated using this technique is limited by the modulus $M$.

In this problem you are given sets of values for $Z$, $I$, $M$, and the seed $L$. Each of these has no more than four digits. For each set of values, determine the length of the cycle of pseudo-random numbers that will be generated. But be careful — the cycle might not begin with the seed!

Each input line contains four integer values, in order: $Z$, $I$, $M$, and $L$. The last line contains four zeroes and marks the end of the input data. $L$ is always less than $M$.

For each input line, print one line in the format Case N: L, where $N$ is the case number (numbered sequentially starting from 1) and $L$ is the length of the sequence of pseudo-random numbers before it begins to repeat.