Consider the sequence of numbers ai
= 0, 1, 2, …, which satisfies the following requirements:
- a0 = 0
- a1 = 1
- a2i = ai
- a2i+1 = ai + ai+1
for every i
= 1, 2, 3, … .
Write a program which for a given value of n finds
the largest number among the numbers a0, a1, …, an.
You are given several test cases (not more than 10 000). Each test case is a line containing an integer n (1 ≤ n < 1018).
The last line of input contains 0.
For every n in the input write the corresponding maximum value found.
This problem is the same as 1079 “Maximum
” but with bigger limitations.
Problem Author: Prepared by Vladimir Yakovlev