Calgary Collegiate Programming Competition 2020 — Open Division

Start

2020-03-14 10:00 AKDT

Calgary Collegiate Programming Competition 2020 — Open Division

End

2020-03-14 14:00 AKDT
The end is near!
Contest is over.
Not yet started.
Contest is starting in -258 days 23:28:20

Time elapsed

4:00:00

Time remaining

0:00:00

Problem G
Fibonacci Cycles

Yraglac loves number sequences. One of his favourites is the classic Fibonacci numbers. He likes to set the base case as $F_0 = F_1 = 1$ and $F_ n = F_{n-1} + F_{n-2}$.

Now, one can only list out the same numbers so many times before getting bored, so Yraglac came up with a new game: if he took the sequence of Fibonacci numbers modulo some $k$, what is the index of the first number in the new sequence that gets repeated? Yraglac only considers numbers in the sequence starting from $n=2$ since $F_0 = F_1$ is boring.

Can you write a program to help Yraglac find the answer?

Input

The first line contains a single integer $1 \leq Q \leq 500$, the number of queries to follow.

The next $Q$ lines each contain a single integer $2 \leq k \leq 1\, 000$, the modulo to be used for the query. It is guaranteed that some number in the sequence will be repeated.

Output

For each query, output the $n$ such that $F_ n$ is the first number in the sequence of Fibonacci numbers modulo $k$ that has a repeat at some point in the sequence.

Sample Input 1 Sample Output 1
3
4
13
22
4
5
8