PTR2 - primes triangle (II)

no tags 

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

Input

in the first line integer 1 <= T <= 104, followed by T lines each line contain integer 1 <= n <= 109.

Output

One line contain pair of integers i and j, where i is the row number and j is the column number, 1 based. Or -1 if n is not found in the primes triangle.

Example

Input:
3
3
23
4

Output:
2 1
4 3
-1

if you find time limit is small, you can solve the tutorial version here: www.spoj.com/problems/PTR22/



Added by:abdou_93
Date:2013-06-07
Time limit:1.5s
Source limit:20000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:owner