PTRI - primes triangle (I)

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

If you find Time limit is small here you can solve the tutorial version here: www.spoj.com/problems/PTRI2/


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

hide comments
2013-06-08 12:08:00 Robert Gerbicz
I know what means SIGSEGV. But I can get also SIGABRT, could you check that all input file is correct so 1<=n<=100000000 is valid and you give exactly T values? Though the single code that only check this doesn't give this error.
And could you set up this problem in the tutorial section with much higher time limit? Let's say 2 seconds for each input set. I would suggest the same for your other super sharp problems.

(abdou)-->all input file now is correct , i found in one of my files some negative integers , i'm so sorry .. soon i will add some of my problem in tutorial section with easy constrain .

Last edit: 2013-06-08 01:28:10
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.