이것이 영원히 계속될 수는 없다

먼 옛날, 아주 먼 은하계의 어느 행성에는 타예(taye) 라는 인기 애완동물이 살았습니다. 타예는 싹을 틔우듯(budding) 번식합니다. 어린 타예가 부모에게서 떨어져 나오면 정확히 한 단위 시간이 지나야 번식할 수 있을 만큼 자라며, 새로운 싹이 자라 부모에게서 분리되는 데 걸리는 시간도 정확히 같습니다. 타예는 사실상 영원히 살기 때문에, 주인들은 언젠가 자신이 갖게 될 타예의 수를 세어 보고 싶어 합니다. 시각 $0$ 에는 타예가 하나도 없고, 시각 $1$ 에 친구가 갓 싹튼(아직 다 자라지 않은) 타예 한 마리를 주었다고 합시다.

그러면 내가 가진 타예의 수는 다음 점화식을 따릅니다.

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

이 값들이 바로 피보나치 수입니다. 이 점화식을 고정된 나머지 $m$ 아래에서(모든 값을 $m$ 으로 나눈 나머지로) 계산하면, 나머지들의 수열은 언젠가부터 되풀이되기 시작합니다. 질문은 이것입니다. 수열이 다시 반복되기 전까지 한 주기의 길이는 얼마일까요?

처음 몇 개의 수열은 다음과 같습니다.

입력으로 주어지는 각 나머지에 대해, 이 수열의 가장 작은 주기의 길이를 구해 출력하세요.

입력은 여러 줄로 이루어지며, 줄 수는 정해져 있지 않습니다. 각 줄에는 정수 $m$ 하나가 주어지고 $2 \le m \le 16777216$ ($2^{24}$) 를 만족합니다. 마지막 줄에는 $0$ 이 주어지는데, 이는 입력의 끝을 나타내며 처리하면 안 됩니다.

입력의 각 나머지 $m$ 에 대해, 나머지 값과 공백 한 칸, 그리고 $m$ 으로 나눈 피보나치 수열의 가장 작은 주기 길이를 차례로 출력하세요.