La sucesión de Fibonacci se define como:

 F0​=0

 F1​=1

 Fn​=Fn−1​+Fn−2​ para n≥2.

Aunque los números de Fibonacci crecen extremadamente rápido, si calculamos el resto de estos números al dividirlos por un entero m, obtenemos una secuencia periódica. Esta secuencia se conoce como el Periodo de Pisano.

Por ejemplo, si m=3, la secuencia de Fibonacci es: 0,1,1,2,3,5,8,13,21,34… Al aplicar el módulo 3 (Fn​(mod3)): 0,1,1,2,0,2,2,1,0,1…

Observa que la secuencia se repite después de 8 términos (0,1,1,2,0,2,2,1). Por lo tanto, el periodo de Pisano para m=3 es 8.

Tu tarea es escribir un programa que, dado un número entero m, encuentre la longitud del periodo de Pisano.

La entrada comienza con una línea que contiene un número entero C, la cantidad de casos de prueba.

Cada una de las siguientes C líneas contiene un número entero m.

Se garantiza que:

• 1≤C≤100
• 2≤m≤1000

Para cada caso de prueba, imprimir:

Caso X: L

Donde X es el número de caso y L es la longitud del periodo de Pisano para m.