Page not loading? Try clicking here.
Placeholder

#1901

Prime number 1s 64MB

Problems

A prime number is a number greater than or equal to 2 that has no divisors other than 1 and itself.

Write a program that, for a given number 𝑀, finds the prime number(s) closest to 𝑀 according to the following conditions.


Input

The first line contains an integer N (1 \le N\le 100)Β , the number of values to process.

The next N lines each contain a single positive integer M_i (1 ≀ M_i ≀ 1\,000\,000).

  • All input values are guaranteed to be within the given ranges.


Output

For each input number M_i​, print the prime number(s) closest to M_i.

  • If multiple primes are equally close, print all of them in increasing order.

  • Each output prime number must be between 1 and 1,000,000 inclusive.


Example 

2 

8 

15
7 

13 17


Source

JUNGOL

You must sign in to write code.