Fibonacci Divisibility Advanced

The task is just the same as Fibonacci Divisibility, however, input values here are greater to prevent you from implementing straightforward calculations using long arithmetics (this allows users in Java or Python to solve the mentioned task easily enough).

You should implement solution which works fast. A second or two is sufficient to run the proper solution (even with not very modern computer).

Hint: you need not long arithmetic for this task.

Input data in the first line will contain the number of test-cases.
Next line will contain exactly this of divisors M for which you should give answers.
Answer should contain indices of members of Fibonacci Sequence, separated by spaces.

Example:

input data:
2
233328 433156

answer:
1620 282

Values will not exceed 2000000.