Given an integer n, with 0 <= n <= 4*10^9, your task is to find the smallest prime number which is not less than n.

The first line of input will be a number specifying the number of lines that follow. Each of the following lines will be an integer n.

For each of these lines, output the smallest prime not less than n, on a separate line.

University of Waterloo Local Contest 2012.7.15