POLSKI SPOJ

Jaś jest ciekawskim dzieckiem, ale zbyt często naprzykrza się rodzicom swoimi pytaniami. Bardzo lubi on też matematykę i ojciec zadał mu zagadkę w nadziei, że dziecko da mu spokój na dłuższy czas. Ojciec podał Jasiowi pewną liczbę pierwszą p i spytał, jaka jest najmniejsza potęga dwójki, która daje resztę jeden przy dzieleniu przez p. Jaś zaczął po kolei mnożyć i dzielić, mnożyć i dzielić...ale nagle wpadł na pomysł, by poprosić pewnego informatyka o pomoc w tej sprawie – oczywiście chodzi o Ciebie. Ale się ojciec zdziwi tym szybkim rozwiązaniem.

Wejście

W pierwszej linii wejścia podana jest liczba N (1<=N<=100) zestawów danych. W każdym z kolejnych N wierszy występuje pojedyncza liczba pierwsza p (2<p<10⁹) zadana przez ojca Jasia.

Wyjście

W kolejnych N liniach wyjścia należy podać odpowiedzi do każdego zestawu danych: po jednej liczbie całkowitej oznaczającej najmniejszą niezerową potęgę dwójki (wykładnik), która daje resztę jeden przy dzieleniu przez p.

Przykład

Wejście:
3
7
11
17

Output:
3
10
8