Smallest Prime Queries

You are given Q queries. For each query, you need to find the smallest prime number that is greater than or equal to a given integer x.

A prime number is a natural number greater than 1 that has no divisors other than 1 and itself. In mathematical terms, a number n is prime if and only if

( n > 1 ) and ( \forall d ; (1 < d < n) \Rightarrow d \nmid n ).

Your task is to process all queries and output the answer for each query, in the same order as given.

inputFormat

The input is given from standard input (stdin) and consists of multiple numbers:

• The first line contains an integer Q (1 ≤ Q ≤ 10⁵), representing the number of queries.
• The next line (or lines) contains Q integers: x₁, x₂, ..., x_Q (1 ≤ x ≤ 10⁶), where each number is a query.

The queries may be space-separated or each on a separate line.

outputFormat

For each query, output the smallest prime number that is greater than or equal to the query integer. The answers should be printed to standard output (stdout) in one line, separated by a single space.

1
5

5