Kawałek szkła glazurowanego o rozmiarze $n$ spada z powietrza i rozpada się na lśniące kryształki, przy czym rozmiar każdego kryształka jest liczbą całkowitą dodatnią.

Aya bierze do ręki te błyszczące kryształki. W jej oczach kryształek o rozmiarze $x$ jest „piękny” wtedy i tylko wtedy, gdy $x$ jest liczbą nieparzystą większą od 1.

Przy założeniu, że wszystkie kryształki są piękne, Aya chce poznać maksymalną możliwą liczbę kryształków. Jeśli sytuacja, w której wszystkie kryształki są piękne, nie istnieje, należy odpowiedzieć -1.

Wejście

Zadanie zawiera wiele zestawów danych. Pierwsza linia zawiera jedną liczbę całkowitą dodatnią $T$ ($1 \le T \le 10^4$), oznaczającą liczbę zestawów danych.

Dla każdego zestawu danych: Jedna linia zawiera jedną liczbę całkowitą dodatnią $n$ ($1 \le n \le 10^9$), oznaczającą rozmiar szkła glazurowanego, czyli sumę rozmiarów wszystkich kryształków.

Wyjście

Dla każdego zestawu danych: Jedna linia zawiera jedną liczbę całkowitą, oznaczającą maksymalną liczbę kryształków przy założeniu, że wszystkie są piękne. Jeśli taka sytuacja nie istnieje, wypisz -1.

Przykład

Wejście 1

6
1
3
5
7
8
9

Wyjście 1

-1
1
1
1
2
3

Uwagi

Dla $n = 3$, $n = 5$, $n = 7$ maksymalna liczba kryształków wynosi oczywiście 1. Dla $n = 8$ maksymalna liczba kryształków wynosi 2, przy czym rozmiary kryształków to 3 i 5. Dla $n = 9$ maksymalna liczba kryształków wynosi 3, przy czym rozmiary kryształków to 3, 3 i 3.