Competitions

# Power + Euler function

# Sequence

Consider the segment, at the end of which the ones are written. Then till infinity we shall do the next procedure: for each segment with ends **a** and **b** (inside which the numbers are absent) we shall write in the middle the number **a** + **b**. So from the starting segment

we get

Then we get the segment

and so on till infinity. How many times the positive integer **n** will be written on a segment?

#### Input

One positive integer **n** (**n** ≤ `10`

).^{13}

#### Output

The number of times the number **n** appears on a segment.

Input example #1

4

Output example #1

2