A “prime” number is an integer greater than 1 with only two divisors: 1 and itself; examples include 5, 11 and 23. Given a positive integer, you are to print a message indicating whether the number is a prime or how close it is to a prime.
The first input line contains a positive integer,n (n ≤ 100), indicating the number of values to check. The values are on the following n input lines, one per line. Each value will be an integer between 2 and 10,000 (inclusive).
For each test case, output two integers on a line by itself separated by a space. The first integer is the input value and the second integer is as follows:
- If the input number is a prime, print 0 (zero).
- If the input number is not a prime, print the integer d where d shows how close the number is to a prime number (note that the closest prime number may be smaller or larger than the given number).