Archiwum zadań programistycznych WWSI

Wykładowcy akademiccy miewają doprawdy dziwne przyzwyczajenia. Otóż jeden z nich, prowadzący zajęcia z algorytmów niestosowanych, ma w zwyczaju pytać studentów w bardzo charakterystyczny sposób: odlicza kolejne liczby pierwsze (zaczynając od 2 i naturalnie nie licząc pustych miejsc) i pechowiec na którym taka liczba wypadnie wędruje ku uldze reszty pod tablicę.

Scenariusz, według którego odbywa się cały proces odpytywania jest zazwyczaj dosyć prosty: odliczanie zaczyna się od prawego dolnego rogu (z perspektywy profesora), numer 2 - do odpowiedzi - znowu się nie nauczyłeś?! Dwója, wyjdź i nie pokazuj się na zajęciach dopóki się nie nauczysz! Numer 5 - do odpowiedzi - Ty też nic nie umiesz?! Dwója, idź się uczyć razem z tym poprzednim! Numer 10 - do odpowiedzi... tak oto odpytywanie trwa w najlepsze i nikt nie wie kiedy padnie na niego kolej ponieważ profesor po dojściu do studenta siedzącego najbliżej lewego górnego rogu najzwyczajniej w świecie przenosi odliczanie na tego, który jest najbliżej prawego dolnego rogu auli i cała zabawa trwa dalej.

Naszemu wybitnemu studentowi - Jasiowi grozi 2 na semestr z algorytmów niestosowanych i absolutnie nie może on pozwolić sobie na kolejną ocenę niedostateczną z odpowiedzi. Jaś oczywiście nic nie umie - tak jak cała reszta studentów ale Jaś jest sprytny... i wyjątkowo zdesperowany. Nasz bohater znając metodykę jakiej profesor używa podczas wybierania kolejnych "kandydatów" do odpowiedzi i wiedząc, że aula będzie pełna i że nikt nic nie umie postanowił grać na zwłokę. Wejdzie do auli pierwszy i zajmie takie miejsce aby odpowiadać jako ostatni, co powinno dać mu dostatecznie dużo czasu aby przyswoić materiał pozwalający na zaliczenie w stylu "PanDa 3". Plan jest genialny! Posiada tylko jeden mały szkopuł - Jaś nie ma pojęcia które to może być miejsce... Pomóż naszemu studentowi i napisz program który wyznaczy optymalne w tej trudnej sytuacji siedzenie. Miejsca w auli ponumerowane są od 1 do n zaczynając od prawego dolnego rogu z perspektywy profesora.

Wejście

W pierwszej linii wejścia znajduje się liczba n (1 ≤ n ≤ 9) określająca liczbę zestawów danych. W każdej z kolejnych n linii znajduje się liczba m (1 ≤ m ≤ 10⁵) określająca liczbę miejsc w auli (początkowo aula zawsze jest pełna, tak więc jest to również ilość studentów). W testach do zadania nie występuje przypadek, w którym i n i m mają maksymalne wartości.

Wyjście

Dla każdego zestawu danych należy w oddzielnej linii wypisać jedną liczbę określającą numer miejsca jakie powinien zająć nasz bohater aby odpowiadać jako ostatni.

Przykład

Wejście:

3
8
9
10

Wyjście:

8
7
1