primes triangle is a triangle that contain all prime numbers .

          2

         3 5

      7 11 13

   17 19 23 29

  .........

you task is very easy given an integer from 1 to 10^8 prints its place in the primes triangle .

Input

in the first line integer 1<= T <= 10^5  , followed by T lines each line contain integer 1 <= n <= 10^8 .

Output

one line contain pair of integers i , j .where i is the row number and j is the column number , 1 base . or -1 if n not exist in the primes triangle .

Example

Input:
3

3

23

4

Output:
2 1

4 3

-1

if you find Time limit is small here you can solve the tutorial version here :

 http://www.spoj.com/problems/PTRI2/