Numery stron

Limit pamięci = 64 MB

Szalony Filozof Bajtolomeusz postanowił spisać w wielkiej księdze wyniki swoich przemyśleń (bo nie lubił dzieci i chciał żeby musiały się o nim uczyć w szkole). Ważny jest sposób numerowania stron księgi, ponieważ jedna z mądrości, które Bajtolomeusz odkrył w swoim szalonym umyśle, mówi, że liczby, które mają w zapisie binarnym dwie jedynki obok siebie, są przeklęte!
22 = 10110 <- przeklęta
9 = 1001 <- OK

Oczywiście księga nie może zawierać stron o przeklętych numerach, bo ich wpływ wypaczyłby światłe nauki filozofa.
Odpowiedz na pytanie: "jaki numer strony może nastąpić po numerze X?" czyli znajdź najmniejszy (żeby nie było niewykorzystanych numerów stron) taki Y, że:
- Y > X - następny numer musi być większy
- Y nie jest przeklęty, czyli nie ma dwóch jedynek obok siebie w zapisie binarnym (X może być przeklęty)

Wejście

W pierwszej linii wejścia znajduje się liczba: N (1 <= N <= 100 000) - liczba numerów. W kolejnych N liniach znajdują się liczby całkowite Xi.

Wyjście

Wyjście powinno zawierać N linii, w których będą liczby całkowite Yi spełniające warunki z treści.

Przykład

IN:
IN:
6
1
2
3
4
5
16

OUT:
2
4
4
5
8
17
Wyjaśnienie przykładu:
1 = 1 -> 10 = 2
2 = 10 -> 100 = 4
3 = 11 -> 100 = 4
4 = 100 -> 101 = 5
5 = 101 -> 1000 = 8
16 = 10000 -> 10001 = 17