Spunem ca un numar natural este dublu-putere daca se poate scrie ca suma a doua puteri distincte ale lui 2, adica sub forma 2^x + 2^y, cu x != y (de exemplu 3 = 1 + 2, 10 = 2 + 8, 1040 = 16 + 1024).
Se da un sir de n numere naturale. Pentru fiecare element A al sirului, determinati cel mai mic numar dublu-putere care este mai mare sau egal cu A.
- Date de intrare
- Pe prima linie se afla n, iar pe a doua linie cele n numere ale sirului.
- Date de iesire
- Se afiseaza pe o singura linie n numere separate prin cate un spatiu: raspunsurile pentru elementele sirului, in ordinea citirii.
- Restrictii
- 1 <= n <= 200 000 0 <= A < 1 000 000 000
Exemple
Exemplul 1
Intrare
7 13 7 6 20 2 33 100
Iesire
17 9 6 20 3 33 129
Exemplul 2
Intrare
4 0 1 3 4
Iesire
3 3 3 5