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⁹ prints its place in the primes triangle .

Input

in the first line integer 1≤ T ≤ 10⁴, followed by T lines each line contain integer 1 ≤ n ≤ 10⁹.

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