Problem description

Gdy zaczyna się lato, a z latem wakacje i sparingów nie ma już tyle, student Igor musi znaleźć sobie inne źródło utrzymania. Zagląda wtedy do swojego magicznego kuferka, w którym codziennie znajduje N dodatnich liczb naturalnych. Niegdyś Igor po prostu oddawał znalezione przez siebie liczby innemu studentowi, Krzysztofowi, który sprzedawał je na bazarku. Krzysztof zawsze wyznawał ideologię, zgodnie z którą liczbę x można sprzedać tylko i wyłącznie za dokładnie x student coinów. Szybko się jednak okazało, że najlepsze liczby, to liczby nieparzyste, a że konkurencja na bazarku nigdy nie należała do najmniejszych, to liczby parzyste w ogóle się nie sprzedawały. Z drugiej strony liczby nieparzyste zawsze sprzedawały się w mgnieniu oka. Igor wpadł więc na pomysł, by rozłożyć każdą z liczb przed wypuszczeniem ich na rynek. Narzędzia którymi dysponuje pozwalają mu rozłożyć świeżo wyciągniętą z kuferka liczbę na co najwyżej dwie liczby, których iloczyn równy jest oryginalnej liczbie. Czyli na przykład liczbę 6 można rozłożyć na liczby 2 i 3, oraz na liczby 1 i 6. Dalsze rozkładanie wpłynęłoby niekorzystnie na pożądane właściwości liczb, wobec czego stałyby bezwartościowe. Chytrzy studenci chcieliby oczywiście zarobić jak najwięcej, do tej pory nie odkryli jednak algorytmu optymalnego rozkładania liczb. Poprosili więc Ciebie o napisanie programu, który dla każdej z liczb policzy maksymalny zysk, który można dzięki niej uzyskać.

Wejście

W pierwszym wierszu wejścia znajduje się liczba N oznaczająca ilość liczb w magicznym kuferku. W drugim wierszu znajduje się N liczb, i-ta z nich oznaczana jest niżej jako a_i.

Wyjście

Na wyjście należy wypisać N liczb, i-ta z nich powinna być maksymalnym zyskiem możliwym do uzyskania dzięki liczbie a_i

Ograniczenia

1 ≤ N ≤ 10⁶, 1 ≤ a_i ≤ 10¹⁸

Podzadania

Przykład

3
2 6 10

1 3 5