Fișierul intrare/ieșire	maximum.in, maximum.out	Sursă	acm.timus.ru
Autor	Emil Kelevedjiev | Vladimir Yakovlev	Adăugată de	Spatarel Dan-Constantin • spatarel
Timp de execuție pe test	0.4 sec	Limită de memorie	2000 KB
Scorul tău	N/A	Dificultate	N/A

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Maximum

Fie șirul de numere A definit astfel:

A₀ = 0
A₁ = 1
A_{2 * i} = A_i
A_{2 * i + 1} = A_i + A_{i + 1}

Scrieți un program care pentru un număr natural N dat găsește numărul M, maximul dintre numerele A₀, A₁, ..., A_N.

Date de intrare

Datele de intrare se citesc din fișierul maximum.in:

• pe prima linie se găsește un număr intreg T;
• pe fiecare dintre următoarele T linii se găsește câte un număr intreg N.

Date de ieșire

Datele de ieșire se tipăresc în fișierul maximum.out

• pe fiecare dintre primele T linii se găsește câte un număr M, corespunzător unui număr N din fișierul de intrare.

Restricții

• 1 ≤ T ≤ 10 000
• 1 ≤ N ≤ 10¹⁸
• Pentru 40% din teste se garantează că: 1 ≤ T ≤ 10 și 1 ≤ N ≤ 100 000

Exemplu

Explicație

A₀ = 0
A₁ = 1
A₂ = 1
A₃ = 2
A₄ = 1
A₅ = 3
A₆ = 2
A₇ = 3
A₈ = 1
A₉ = 4
A₁₀ = 3

Dacă N = 5, atunci M = max(0, 1, 1, 2, 1, 3) = 3.
Dacă N = 10, atunci M = max(0, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3) = 4.