의사 난수

컴퓨터는 보통 진짜로 무작위한 수를 만들어 낼 수 없지만, 실용적으로는 무작위처럼 보이는 의사 난수(pseudo-random number) 수열을 생성하는 데 자주 쓰입니다. 이런 수열은 어떤 알고리즘으로 만들어지지만, 모든 실용적인 목적에서 진짜 무작위처럼 보입니다. 난수는 시뮬레이션을 비롯한 다양한 분야에서 사용됩니다.

널리 쓰이는 의사 난수 생성 기법으로 선형 합동법(linear congruential method)이 있습니다. 마지막으로 생성된 의사 난수가 $L$이라면, 다음 수는 $(Z \times L + I) \bmod M$을 계산하여 얻습니다. 여기서 $Z$는 곱하는 상수, $I$는 더하는 상수, $M$은 나머지를 취하는 상수(모듈러스)입니다.

예를 들어 $Z = 7$, $I = 5$, $M = 12$이고 첫 번째 난수(보통 시드(seed)라고 부릅니다)가 $4$라면, 이후의 의사 난수들은 다음과 같이 정해집니다.

마지막 난수 L | (Z×L+I) | 다음 난수 (Z×L+I) mod M
--------------|---------|------------------------
      4       |   33    |           9
      9       |   68    |           8
      8       |   61    |           1
      1       |   12    |           0
      0       |    5    |           5
      5       |   40    |           4

보다시피 이 기법으로 생성되는 의사 난수 수열은 여섯 개의 수마다 반복됩니다. 이 기법으로 만들 수 있는 수열의 최대 길이는 모듈러스 $M$으로 제한된다는 것을 알 수 있습니다.

이 문제에서는 $Z$, $I$, $M$, 그리고 시드 $L$의 값이 여러 묶음 주어집니다. 각 값은 네 자리 이하입니다. 각 묶음에 대해, 생성되는 의사 난수가 반복되기 시작할 때까지의 주기(cycle) 길이를 구하세요. 단, 주기가 시드에서 시작하지 않을 수도 있으니 주의하세요!

입력의 각 줄에는 네 개의 정수 $Z$, $I$, $M$, $L$이 이 순서대로 주어집니다. 마지막 줄에는 네 개의 $0$이 주어지며, 이는 입력 데이터의 끝을 나타냅니다. $L$은 항상 $M$보다 작습니다.

각 입력 줄에 대해 Case N: L 형식으로 한 줄씩 출력하세요. 여기서 $N$은 테스트 케이스 번호(1부터 순서대로 매깁니다)이고, $L$은 수열이 반복되기 시작하기 전까지의 의사 난수 개수입니다.