The well known Fibonacci numbers are defined recursively as follows:
*F*_{0} = 0, *F*_{1} = 1, *F*_{i} = *F*_{i−1} + *F*_{i−2} for *i* ≥ 2.
The first Fibonacci numbers are 0, 1, 1, 2, 3, 5, 8, 13, 21, ….

Let us generalize the Fibonacci numbers.
For every pair of natural numbers *a* and *b*,
define the sequence *S*(*a*, *b*) = [*f*_{0}, *f*_{1}, …] as
*f*_{0} = *a*, *f*_{1} = *b*,
*f*_{i} = *f*_{i−1} + *f*_{i−2} for *i* ≥ 2.
Note that *S*(0, 1) is the traditional Fibonacci sequence.

You are given a natural number *n*.
Please compute how many pairs (*a*, *b*) exist
such that *S*(*a*, *b*) has a *i* ≥ 3 where *f*_{i} = *n*.
For instance, for *n* = 2 there are exactly three such sequences:
*S*(0, 1) = [0, 1, 1, 2, …],
*S*(1, 0) = [1, 0, 1, 1, 2, …],
and *S*(2, 0) = [2, 0, 2, 2, …].

**Input**

Input consists of several cases,
each with a different natural number *n* between 1 and 10^{6}.

**Output**

For every *n*,
print the number of pairs (*a*, *b*)
such that *n* appears at a position *i* ≥ 3 in *S*(*a*, *b*).

**Hint**

Depending on your solution, Cassini’s identity could be useful:
*F*_{i−1} · *F*_{i+1} − *F*_{i}^{2} = (−1)^{i}.

Public test cases

**Input**

2 1 3 9 10 1000 1000000

**Output**

3 1 4 8 10 780 773883

Information

- Author
- Salvador Roura
- Language
- English
- Official solutions
- C++
- User solutions
- C++
- Event
- Catorzè Concurs de Programació de la UPC - Final
- Date
- 2016-09-21