# Fibonacci Sequence

Problem #67

Tags: arithmetic data-structures long-numbers classical

Who solved this?

Also available in: Russian

Even beginner programmers are usually acquainted with the Fibonacci Sequence which is generated as following:

• 0-th value is `0`;
• 1-st value is `1`;
• all next values are sum of two immediately preceeding.

So we have:

``````0: 0
1: 1
2: 1 = 0 + 1
3: 2 = 1 + 1
4: 3 = 1 + 2
5: 5 = 2 + 3
6: 8 = 3 + 5
``````

and so on, so if you continue calculations yourself, you get the the beginning of the sequence like this:

``````0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ...
``````

One easily notes that values grow fast! The `17-th` value already exceeds `thousand`, the `31-st` is larger than `million`.

Problem statement

You will be given several Fibonacci numbers. Your task is to tell their indices in the sequence.

Input data contain the amount of Fibonacci numbers to process.
Next lines contain one Fibonacci number each (from the first `1000` values).
Answer should contain their indices in the sequence, separated by spaces.

Example:

``````input data:
5
610
34
0
1346269
10946