Limits
1s, 512 MB
A prime number is a positive integer that is divisible only by itself and 1. The first few prime numbers are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 and so on.
You will be given an integer N. You need to find the largest prime number that is smaller than N and the smallest prime number that is larger than N.
Input
The first line of input contains an integer T which denotes the number of test cases.
The first and only line of each test case contains a single integer N which denotes the number.
Constraints:
1 <= T <= 50
10 <= N <= 500
Output
For each test case, print a single line containing two integers - the largest prime number that is smaller than N and the smallest prime number that is larger than N.
Sample
| Input | Output |
|---|---|
5 10 11 12 19 25 | 7 11 7 13 11 13 17 23 23 29 |
