The 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^8 print 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 is not found in the primes triangle.

Example

Input:
3
3
23
4

Output:
2 1
4 3
-1