# Extended Fibonacci numbers P25832

Statement html

The well known Fibonacci numbers are defined recursively as follows: F0 = 0, F1 = 1, Fi = Fi−1 + Fi−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) = [f0, f1, …] as f0 = a, f1 = b, fi = fi−1 + fi−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 fi = 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 106.

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: Fi−1 · Fi+1Fi2 = (−1)i.

Public test cases
• Input

```2
1
3
9
10
1000
1000000
```

Output

```3
1
4
8
10
780
773883
```
• Information
Author