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
2022-05-24 17:25:39 Ishan
fast i/o is a must, tried everything, finally fast i/o did the trick.
2014-02-09 17:10:59 [Lakshman]
@abdou 00 Time Limit is very strict it should be at least .5s ?

abdou 00 can you please Tell me whether my Sieve is slow or or the method I am using to find the position in the triangle is slow?

Thanks.
2014-01-17 05:28:11 [Lakshman]
@Mehmet http://www.spoj.com/problems/PTRI2
2014-01-16 17:04:50 mehmetin
Tutorial version link is dead.
2013-07-26 15:36:00 Mitch Schwartz
@fitcat: The time limit is strict, but changing it now is a bad idea, as some people have already worked hard to pass within it. The tutorial version does have different data from this one, I don't know why; my recommendation is to focus more on the 0.2s than on the overall time.
2013-07-26 05:30:18 fitcat
Even my program ran in 0.70s (better than the 3rd AC one) in the tutorial version, still got TLE. Are the test cases different? If not, is it possible to relax the time limit on the total time instead of the individual time?

Edit: added the text in the bracket to make it more clear.

Edit: @Mitch: Thanks. I will try harder.

Last edit: 2013-07-27 08:12:35
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.