Wróżka

Treść

Wróżka Primelia już od wielu lat jest znana z wyjątkowej trafności swych przepowiedni. Owa trafność nie jest dziełem przypadku. Oprócz wrodzonych zdolności Primelia stosuje wiele innowacyjnych technik wróżbiarskich. Ostatnią nowinką jaką nasza bohaterka wprowadziła do świata szklanej kuli i tarota jest primologia – numerologia oparta na własnościach liczb pierwszych. Aby móc skorzystać z tej techniki wróżka musi wpierw dla zadanej liczby l, np. roku narodzin, wyznaczyć l-tą liczbę pierwszą. O ile dla małych wartości l zadanie to jest względnie proste, o tyle przy większych liczbach staje się wręcz niemożliwe do wykonania. Z tego właśnie powodu Primelia postanowiła zwrócić się o pomoc do najlepszych programistów startujących w Podlaskim Turnieju w Programowaniu Zespołowym. Napisz program, który dla podanej liczby l wyznaczy l-tą pod względem wielkości liczbę pierwszą.

Wejście

Dane podawane są na standardowe wejście. W pierwszym wierszu podana jest liczba N (1<=N<=10000) zestawów danych. Dalej podawane są zestawy danych zgodnie z poniższym opisem:

Jeden zestaw danych

Pierwszy i jedyny wiersz zestawu danych zawiera liczbę całkowitą l (1<=l<=5·10⁷). Można założyć, że podane liczby nie powtarzają się i są rozłożone wzdłuż całego zakresu dozwolonych wartości.

Wyjście

Wyniki programu powinny być wypisywane na standardowe wyjście. W kolejnych wierszach należy podać odpowiedzi obliczone dla kolejnych zestawów danych. Wynikiem dla jednego zestawu jest l-ta co do wielkości liczba pierwsza, gdzie l jest liczbą na wejściu.

Przykład

dane wejściowe:
3
1000
1
50000000

wynik:
7919
2
982451653