## Fibonacci Divisibility AdvancedProblem #71 |

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`

.

You need to login to get test data and submit solution.