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++