C - Gra w liczby

Jaś i Małgosia, studenci Politechniki, podczas nudnego wykładu (z litości nie podamy tu jakiego) wymyślili grę. Jej zasady są następujące: gracze na przemian podają liczby naturalne, przy czym podana liczba musi być mniejsza od liczby poprzednika, ale większa od jej pierwiastka. Gracz, który nie może podać takiej liczby przegrywa.

Jaś chce zaimponować Małgosi i wymyśleć strategię wygrywającą. Niestety nie udaje mu się to. Pomóż mu i napisz program, który dla podanej liczby poda następną liczbę (odpowiedź), która daje największe prawdopodobieństwo wygranej. W przypadku kilku takich liczb należy podać największą z nich.

Wejście

W pierwszej linii znajduje się jedna liczba całkowita n, oznaczająca liczbę zestawów danych.
W kolejnych wierszach znajdują się zestawy danych - liczby podane przez Małgosię (większe od 2 ale mniejsze od 2.000.000.000):

Wyjście

Dla każdego zestawu danych należy wypisać odpowiadającą mu liczbę dającą największe prawdopodobieństwo wygranej.

Przykładowy test

3
3
10
16

Wynik 

2
4
15