아래는 백만 사용자를 가진 어느 전화 회사 시스템의 사용기록입니다:

n번째 사용기록의 건 사람 번호와 받은 사람 번호는 각각 Caller(n) = S_2n-1과 Called(n) = S_2n입니다. 여기서 S_1,2,3,...은 "지연 피보나치 생성기(Lagged Fibonacci Generator)"의 항입니다:

1 ≤ k ≤ 55일 때, S_k = [100003 - 200003k + 300007k³] (modulo 1000000)
56 ≤ k일 때, S_k = [S_k-24 + S_k-55] (modulo 1000000)

만일 Caller(n) = Called(n) 이라면 잘못 걸었다고 가정합니다; 이외의 경우는 모두 정상적으로 성공한 통화입니다.

사용기록에서, X가 Y에게 또는 반대로 Y가 X에게 전화를 걸었다면 둘은 친구입니다. 이런 식으로 X가 Y의 친구이고 Y가 Z의 친구라면 X는 Z와 친구의 친구입니다. 친구관계는 이렇게 계속 연결될 수 있습니다.

시장님의 전화번호는 524287 입니다. 99%의 사용자(시장님을 포함하여)가 시장님의 친구거나, 친구의 친구거나, ... 이런 친구 관계가 되려면 성공적인 통화가 몇 번이나 이루어져야 합니까? 잘못 건 전화는 통화 수에서 제외합니다.