Olympic Lottery
Whoever takes a pack of tickets will receive – a water tower...
Film "The Diamond Arm"
In a remarkable event organized by lottery officials in London, a record was set during the night of July 27, coinciding with the opening ceremony of the 2012 Olympic Games. A lottery draw took place, resulting in the creation of one hundred millionaires in the UK in a single night.
This special Olympic edition of the EuroMillions Millionaire Raffle awarded one hundred checks, each worth one million pounds. The scale of this draw and the size of the prizes were not coincidental; they served as a gesture of appreciation to the UK citizens who participated in national lotteries. The funds raised from these lotteries contributed to the development of sports infrastructure, a crucial part of the Olympic preparations. The total cost of organizing the London Olympics was estimated at several billion pounds, with the National Lottery contributing approximately 2.2 billion pounds towards these expenses.
Vasya, a young programmer who arrived at the Olympics before the opening, decided to try his luck in the Olympic lottery. Through some mysterious channels, he learned that only tickets with prime numbers would be winners. After observing the ticket number of the person ahead of him in line, Vasya needs to quickly determine how many people he should let pass to secure a ticket with a prime number. To do this, he needs to find the next prime number after the observed ticket number, and he seeks your assistance. Help Vasya find the next prime number.
Input
The first line contains the number of test cases T (0 ≤ T ≤ 1049). The following T lines each contain a single number, representing the ticket number observed N (0 ≤ N ≤ 4·10^9).
Output
For each test case, output the number of the next potential lucky lottery ticket, without leading zeros, on a separate line.