Хто візьме білетів пачку, той одержить – водокачку…

к/ф "Діамантова рука"

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

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

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

Вхідні дані

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

Вихідні дані

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