TWINP - TWIN PRIMES

no tags 

Twin Primes are the pair of prime numbers that differ by two. For ex.

3,5

11,13

29,31

(each differ by two)

Input

First line of input consists of T (number of test cases).

Next T lines contains a single number N (indicating the Nth pair of twin primes).

Output

For every test case output the pair of Twin Primes in each line separated by a single space.

Example

Input:

3
1
7
11

Output:

3 5
59 61
137 139


(T<=25,1<=N<=10^5)

(Try tutorial version (time limit easy) -> http://www.spoj.com/problems/TWINP2/ )

hide comments
[Lakshman]: 2013-04-18 18:24:48

Got AC...I initially I was trying Rabin Miller I think the Twins prime would be less then <100000; when tried all n up to 100000 Used sieve to pass the time limit.

(Tjandra Satria Gunawan)(曾毅昆): 2012-08-30 17:28:22

@numerix: Thanks for your explanation. :-) For me, this problem is hard enough, my submissions give me (6 TLE and 6 WA) finally AC with 1,86s time.

numerix: 2012-08-30 14:51:51

@Tjandra: Because it's an easy one. You can get AC with a "normal" (or slightly modified) prime sieve - very straight forward. It could be a classical one if TL and/or SL were stricter.

(Tjandra Satria Gunawan)(曾毅昆): 2012-08-30 11:47:07

why this problem in tutorial? can anyone explain?

RAJDEEP GUPTA: 2012-04-13 18:57:10

what is the answer for n=10^5 ?

sandeep pandey: 2012-04-11 18:30:16

@numerix:i tried same algorithm for C++ and it pass in .97 sec.
same code in java shows TLE.wht does it mean?

numerix: 2012-04-11 09:05:29

@sandeep pandey: If you get TLE with Java, you must optimize your code. There are several Python solutions AC, so it shouldn't be a problem to do it with Java.

sandeep pandey: 2012-04-11 05:19:47

@Problem Setter:Plesae increase the TimeLimit for SlowerLanuage(Java).

Santhana Krishnan: 2012-04-11 05:19:47

@Francky: Did you hard code the primes ? Your time is insane.

Francky: 2012-04-11 05:19:47

It could have been more fun with source limit at 1000B (or even 500B), and 4s time limit for slow langages as Python.
But, nice problem.


Added by:Avinash
Date:2012-04-07
Time limit:0.25s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own Problem