Let's assume that 
 -  *v*(*n*) is the largest prime number, that does not exceed *n*;-  *u*(*n*) is the smallest prime number strictly greater than *n*. 
Find <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/9efda33382293068ce21371b950297a1d3ac3212.png" style="max-width: 100.0%;max-height: 100.0%;"/>.
The first line contains integer *t* (1 ≤ *t* ≤ 500) — the number of testscases. 

Each of the following *t* lines of the input contains integer *n* (2 ≤ *n* ≤ 10<sup class="upper-index">9</sup>).
from math import *
def IsPrime(n):
    k = 0
    for i in range(1,int(sqrt(n)) + 1):
        if n % i==0:k+=1
        if k + 1 > 2:
            return False
    return True
n = int(input())
for i in range(0,n):
    a = int(input())
    u = 1
    t = 0
    for h in range(2,a+1):
        for i in range(h,0,-1):
            if IsPrime(i):break
        for j in range(h + 1,10**9 + 1):
            if IsPrime(j):break
        if h==2:
            v = i * j
            c = i
            d = j
        else:
            c = c // gcd(c,i) * i
            d = d // gcd(d,j) * j
            v = v // gcd(v,i * j) * i * j
            u = v // c + v // d
    print(u,v)
