Кто возьмёт билетов пачку, тот получит – водокачку…

к/ф "Бриллиантовая рука"

Своеобразный рекорд установлен организаторами лотерей в Лондоне. В ночь на 27 июля в рамках церемонии открытия Олимпийских игр 2012 был проведен розыгрыш лотереи, благодаря которому в Великобритании появилось сразу сотня миллионеров.

В олимпийском розыгрыше лотереи EuroMillions Millionaire Raffle были разыграны сто чеков по миллиону фунтов. Столь масштабный розыгрыш и солидные призы не случайны. Они стали, своего рода, благодарностью гражданам Великобритании, принимавшим участие в национальных лотереях, сборы от которых шли на развитие спортивной инфраструктуры. Дело в том, что затраты на организацию Олимпиады в Лондоне оценивались в несколько миллиардов фунтов. Национальная лотерея помогла собрать на эти цели около 2,2 миллиардов.

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

Входные данные

В первой строке находится количество тестовых случаев T (0 ≤ T ≤ 1049), а далее в T отдельных строках по одному числу – номер очередного подсмотренного билета N (0 ≤ N ≤ 4·109).

Выходные данные

Для каждого тестового случая в отдельной строке вывести номер предполагаемого счастливого лотерейного билета без ведущих нулей.