• Шифрование
  CRYPTOGRAPHY

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

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

Технические требования

Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение по времени тестирования: до 5 секунд на один тест

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

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


Пример:

INPUT.TXT
4
3
2
5
7

OUTPUT.TXT
5
3
11
17