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.