[D_E_N_]

Вот такую задачу мне следует выполнить:

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


Технические условия
Входные данные

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

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

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


Информация о задаче
Лимит времени: 1 секунда
Лимит памяти: 64 MB
Баллы за пройденный тест: 4.54545
Источник: II Открытая Дистанционная Олимпиада 2012-2013 им. В.Л.Дидковского
Мои результаты: 0/2

Пример:
Пример входных данных
3
6
20
100

Пример выходных данных
7
23
101
================================================== ========

Сразу стало ясно, что о решетах Эратосфена и Аткина можно забыть.
Но как я ни бился, ничего не получается!
Первая моя реализация: olymp_lotery_v1.zip
Использовалась база простых чисел до sqrt(2*10^9)
Код оказался слишком большим, так что система отказалась принять его

Вторая реализация медленней, воркабельна, но система проверки выдала мне 80% неправильных ответов. Остальные 20% пришлись на истечение лимита времени выполнения программы.
Вот эта реализация: olymp_lotery_v2.zip


Как же быть? На С++ почти не пишу.