The Next Prime

Time limit1sMemory limit128 MB

Summary
For each of several integers n, print the smallest prime number greater than or equal to n.
Level

Medium5 of 10

Topics
Number theory, Math
Solved
No attempts yet

Problem

Given an integer nn (0≤n≤4×1090 \le n \le 4 \times 10^9), write a program that finds the smallest prime number that is greater than or equal to nn.

Input

The first line contains the number of test cases. Each test case consists of a single line containing one integer nn.

Output

For each test case, print the smallest prime that is greater than or equal to nn, one per line.

Examples2

  1. Example 1

    Input
    3
6
20
100
    Expected output
    7
23
101

  2. Example 2

    Input
    5
0
1
2
3
4
    Expected output
    2
2
2
3
5