Extended Fibonacci numbers P25832

The well known Fibonacci numbers are defined recursively as follows: F₀ = 0, F₁ = 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₀, f₁, …] as f₀ = a, f₁ = 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⁶.

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² = (−1)ⁱ.