Програмчлалын олимпиадын бодлогын архив

Дараах дүрмээр өгөгдсөн a[i], i = 0, 1, 2, ..., дарааллыг авч үзье:
a[0] = 0
a[1] = 1
a[2i] = a[i]
a[2i+1] = a[i] + a[i+1]
i=1, 2, 3, ... .
N (0 < N < 10000) бүхэл тоо өгөгдсөн үед a[0], a[1], ..., a[N] тоонууд дотроос хамгийн их утгатайг нь олох програм зохио. 

Input

Оролт нь арваас дээшгүй тооны мөртэй ба мөр тус бүрт ганц N тоо өгөгдөнө. Сүүлийн мөрөнд 0 гэсэн тоо байна.

Output

N тоо бүрийн хувьд олдох хамгийн их утгыг нэг нэг мөрөнд гаргана

Example

Input:
5
10
0

Output:
3
4