При подготовке данного комплекта задач жюри столкнулось со следующей проблемой: нужно было передавать по электронной почте тексты задач. Как известно, электронная почта ненадёжна, сообщения передаются открытым текстом, и существует опасность, что кто-нибудь их перехватит. Членам программного комитета вовсе не хотелось, чтобы задачи стали известны участникам раньше начала соревнования, поэтому они прибегли к методам криптографии. Жюри разработало совершенно новый способ шифрования текста, но он пока не запатентован и поэтому держится в секрете. Впрочем, одну тайну мы вам всё же откроем, новый алгоритм основан на работе с простыми числами и, в частности, использует вычисление n-го по счёту простого числа.

Несколько членов программного комитета, независимо друг от друга, разработали программы, производящие такие вычисления, но эти программы выдают разные ответы. Каждый уверен, что он написал свою программу правильно, поэтому жюри встало в тупик и не может продолжать свою работу.

Вы должны помочь жюри и спасти соревнования. Напишите программу, вычисляющую n-е по счёту простое число, и, самое главное, она должна работать правильно!

В первой строке находится ровно одно целое число k, задающее количество чисел в списке. За ним следуют k целых чисел, по одному в строке. Все числа положительные и не превосходят 15000.

Для каждого числа n из списка вы должны вывести n-е по счёту простое число. Ответ для каждого числа должен находиться в отдельной строке.

Простое число — это целое положительное число, которое имеет ровно два различных положительных делителя, т.е. 1 не является простым числом.