TWINP - TWIN PRIMES

no tags 

Twin primes are the pair of prime numbers that differ by two. For example:

  • 3, 5
  • 11, 13
  • 29, 31

The numbers in each pair 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).

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

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

(Another tutorial version, with limited source code length, at 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:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own Problem