Runda 25 - Wróg u bram

Zawody stałe, runda 25;

Limit czasowy: 1s; Limit pamięciowy: 32MB;

Wróg u bram

Nadeszły ciężkie czasy - nasze piękne miasto zostało oblężone przez wroga. Nieprzeliczone hordy nieprzyjaciół rozstawiły wielobarwne namioty u naszych bram, liczne proporce i flagi zasnuwają niebo niczym dym a ciężki dźwięk ich bębnów napawa nas przerażeniem. Jest jednak nadzieja - nasi przyjaciele wysłali w odsieczy oddział wojska. Wiemy, że biegli są w sztuce wojennej i że z pewnością podzielą swoją armię na kilka sprawnych oddziałów. Posłaniec przekazał nam wieść, że dowódca postanowił podzielić armię na tak duże oddziały, jak to tylko możliwe, wszystkie tej samej liczności. Jeden z nich zostawił w swej twierdzy a reszta właśnie podąża nam na ratunek. Wiemy ilu żołnierzy wysłano, nie wiemy jednak jak liczna była armia przyjaciół przed podziałem, poza tym, że stara tradycja nakazuje armii mieć nieparzystą liczbę żołnierzy. Zastanawiamy się, czy nie było to zbyt ofiarne z ich strony i chcemy policzyć, ilu w najgorszym razie obrońców pozostało w twierdzy.

Wejście:

Pierwsza linia wejścia zawiera liczbę naturalną , oznaczającą liczbę przypadków testowych (). Dane do każdego z nich składają się z jednej linii zawierającej jedną liczbę naturalną (), oznaczającą liczbę żołnierzy przybywającego na odsiecz oddziału.

Wyjście:

Dla każdego przypadku testowego należy wypisać jedną linię z odpowiedzią - minimalną liczbą żołnierzy, jaka mogła pozostać w twierdzy przyjaciela. Jeśli posłaniec coś przekręcił i taka liczba nie istnieje, należy wypisać -1.

Dane przykładowe: