Primes triangle is a triangle that contain all prime numbers.

          2
        3   5
      7   11  13
    17  19  23  29
  ... ... ...

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

Input

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

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/PTR22/