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/
hide comments
Ishan:
20220524 17:25:39
fast i/o is a must, tried everything, finally fast i/o did the trick. 

[Lakshman]:
20140209 17:10:59
@abdou 00 Time Limit is very strict it should be at least .5s ?


[Lakshman]:
20140117 05:28:11
@Mehmet http://www.spoj.com/problems/PTRI2 

mehmetin:
20140116 17:04:50
Tutorial version link is dead. 

Mitch Schwartz:
20130726 15:36:00
@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. 

fitcat:
20130726 05:30:18
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?

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