Sparing w Programowaniu Zespołowym UAM & PP, 6.11.2004

Opis

W pewnym nowoczesnym mieście zbudowano ronda według nowej technologii. Każde rondo ma n lamp. Przed zmierzchem wypuszczany jest robot który te lampy miał włączać. Jednak programista coś namieszał i wyprodukowano serie n robotów które zamiast podchodzić do wszystkich lamp podchodziły tylko do k pierwszych (k - numer seryjny robota) i na dodatek po podejściu do lampy robot przełącza wyłącznik (jeżeli był włączony to wyłącza, jeśli wyłączony to włącza), następnie roboty podchodzą do k następnych lamp i tak w kółka aż nie zostanie im wydany rozkaz zakończenia prac, który jest realizowany po zakończeniu przełączania aktualnych k lamp. Projektanci ronda załamali ręce. Jednak zauważyli, że część robotów jest w stanie zapalić wszystkie lampy (przykładowo dla n=4 wszystkie roboty są w stanie tego dokonać; dla n=3 tylko roboty o numerze seryjnym 1 i 3). Wszyscy wielce uradowaniu już zabrali się do selekcji odpowiednich robotów, gdy Urząd Miasta i Gminy zarządził wielkie oszczędności - na każdym rondzie może palić się tylko jedna lampa. To doszczętnie dobiło zespół. Jednak Ty młody, inteligentny informatyk wiesz, że niektóre roboty nawet to potrafią dokonać. Dlatego też postanowiłeś napisać program który policzy ile z serii n robotów byłoby wstanie obsłużyć rondo o n lampach.

Specyfikacja wejścia

W pierwszej linii znajduje się liczba D, oznaczająca liczbę zestawów danych. Każdy test składa się z jednej linii zawierającej liczbę całkowite N (1 ≤ N ≤ 10^9).

Specyfikacja wyjścia

Dla każdego zestawu danych w osobnej linii wypisz liczbę robotów które mogą obsłużyć rondo o N lampach.

Przykład

2
4
6

2
2