how-many-prime

This is a fact for almost all the students out there that Mathematics subject is a very fearful subject for them.

And no wonder this fact is also true for our friend Primo. But to challenge his fear he went to the Mathe-Matica Town for his summer vacations.

In Mathe-Matica town every person is assigned a Friend Score.

A Friendship Score is an integer value such that 

(i) It is unique and 

(ii) It can not be equal to Friend Score when other Friend Scores are multiplied with each-other

Now our Primo can not enjoy his vacations alone. So he asked help from the Mathe-Matica town Mayor. The Mayor gave him a Friendship Score and told him that he can be friend with two persons of town only and only if the addition of those two persons' Friend Score is equal to the Friendship Score.

Primo is not good in Mathematics so he wants your help to find out his friends in town.

Input : First line of Input contains the Number of Test Cases T .  Next T lines contain a single Integer N. N denotes the Friendship Score

Output : Output Friend Score of his friends in town. If he can not have any friend then print -1 -1 Produce output for each Test Case in a new line.

Note : Output should be in Increasing Order of Friend Scores

Constrains

1 ≤ T ≤50

2 ≤ N ≤ 10^6

Note :- To be Eligible for Prizes you have to register and create your home address maptag.

Click here to create your Maptag

SAMPLE INPUT
3
10
100
1000

SAMPLE OUTPUT
3 7
47 53
491 509

Explanation

Case 1: Friendship Score (= 10) is equal to Friend Score ( 3 + 7)

Case 2: Friendship Score (= 100) is equal to Friend Score ( 47 + 53)

Case 3: Friendship Score (= 1000) is equal to Friend Score ( 491 + 509)

Source: hackerearth | Difficulty: EASY


Solutions:
limit = 1000000
prime = [0] * (limit + 1)
def seive():
	global limit
	global prime
	
	prime[0] = 1
	prime[1] = 1
	
	p = 2
	while p * p  <= limit:
		if prime[p] == 0:
			i = p * 2
			while i <= limit:
				prime[i] = 1
				i += p
		p+=1
		
seive()
for _ in range(eval(input())):
	n = eval(input())
	l = (n - 1) / 2
	r =  n - l
	done = False
	while l > 0  and (prime[l] or prime[r]):
		l -= 1
		r += 1
	if l > 0 and  not prime[l] and  not prime[r]:
		a, b = l, r
	else:
		a, b = -1, -1        
	print("%d %d" % (a, b))
		
			  


def prime(prim):
	c=list(range(2,prim+1))
	for i in range(2,int((prim+1)**0.5)+1):
		c=[x for x in c if x==i or x%i]
	return c
	
for _ in range(eval(input())):
	k=1
	primo=eval(input())
	k=1
	arr=prime(primo)
	arr1=[]
	arr2=[]
	#print "HMM"
	#print arr
	for item in arr:
		if item<=primo/2:
			arr1.append(item)
		else:
			arr2.append(item)
	
	arr1=arr1[::-1]
	for item in arr1:
		for it in arr2:
			if primo==item+it:
				k=5
				break
		if k==5:
			break
	#print arr1
	#print arr2
	if k!=5:
		print("-1 -1")
	else:
		print(str(item) +str(" ")+str(it))