In Omkar's last class of math, he learned about the least common multiple, or $LCM$. $LCM(a, b)$ is the smallest positive integer $x$ which is divisible by both $a$ and $b$.

Omkar, having a laudably curious mind, immediately thought of a problem involving the $LCM$ operation: given an integer $n$, find positive integers $a$ and $b$ such that $a + b = n$ and $LCM(a, b)$ is the minimum value possible.

Can you help Omkar solve his ludicrously challenging math problem?


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \leq t \leq 10$). Description of the test cases follows.

Each test case consists of a single integer $n$ ($2 \leq n \leq 10^{9}$).


-----Output-----

For each test case, output two positive integers $a$ and $b$, such that $a + b = n$ and $LCM(a, b)$ is the minimum possible.


-----Example-----
Input
3
4
6
9

Output
2 2
3 3
3 6



-----Note-----

For the first test case, the numbers we can choose are $1, 3$ or $2, 2$. $LCM(1, 3) = 3$ and $LCM(2, 2) = 2$, so we output $2 \ 2$.

For the second test case, the numbers we can choose are $1, 5$, $2, 4$, or $3, 3$. $LCM(1, 5) = 5$, $LCM(2, 4) = 4$, and $LCM(3, 3) = 3$, so we output $3 \ 3$.

For the third test case, $LCM(3, 6) = 6$. It can be shown that there are no other pairs of numbers which sum to $9$ that have a lower $LCM$.

Difficulty: interview

Starter code:

Solutions:
from math import sqrt
def solve():
    n = int(input())
    for i in range(2, int(sqrt(n)) + 1):
        if n % i == 0:
            x = n // i
            print(x, x * (i-1))
            return 
    print(n-1,1)
for i in range(int(input())):
    solve()

from math import *

def r1(t):
    return t(input())

def r2(t):
    return [t(i) for i in input().split()]

for _ in range(r1(int)):
    n = r1(int)
    i = 2
    a = 1
    b = n - 1
    while i * i <= n:
        if n % i == 0:
            t = n // i
            a = max(a, t)
            b = min(b, n - t)
        i += 1
    print(a, b)


import math
from collections import deque
from sys import stdin, stdout

input = stdin.readline
#print = stdout.write

for _ in range(int(input())):
    x = int(input())
    ind = 2
    mn = 99999999999999
    while ind * ind <= x:
        if x % ind == 0:
            mn = min(mn, ind)
            mn = min(mn, x // ind)
        ind += 1
    if mn == 99999999999999:
        mn = x
    print(x // mn, x - x // mn)

from math import ceil
for _ in range(int(input())):
    n = int(input())
    d = 1
    for i in range(2, ceil(n**(1/2))+1):
        if n % i == 0:
            d = i
            break
    if d == 1:
        print(1, n-1)
    else:
        print(n//d, n-n//d)


import math as mt
import sys,string
input=sys.stdin.readline
from collections import defaultdict
L=lambda : list(map(int,input().split()))
Ls=lambda : list(input().split())
M=lambda : list(map(int,input().split()))
I=lambda : int(input())


t=I()
for _ in range(t):
    n=I()
    f=0
    for i in range(2,int(mt.sqrt(n))+1):
        if(n%i==0):
            f=1
            key=i
            break
    if(f):
        print(n//key,n-n//key)
    else:
        print(1,n-1)


t=int(input())
for you in range(t):
    n=int(input())
    if(n%2==0):
        print(n//2,n//2)
    else:
        l=[1]
        i=2
        while(i*i<=n):
            if(n%i==0):
                l.append(i)
                if(i!=n//i):
                    l.append(n//i)
            i+=1
        z=max(l)
        print(n-z,z)


# for _ in range(1):
for _ in range(int(input())):
    # a, b = map(int, input().split())
    n = int(input())
    # arr = list(map(int, input().split()))
    # s = input()
    i = 2
    g = -1
    while i * i <= n:
        if n % i == 0:
            g = n // i
            break
        i += 1
    if g == -1:
        print(1, n - 1)
    else:
        v = n // g - 1
        print(g, g * v)





from collections import defaultdict as dd
from collections import deque
import bisect
import heapq

def ri():
    return int(input())

def rl():
    return list(map(int, input().split()))


def solve():
    n = ri()
    if n % 2 == 0:
        print(n // 2, n // 2)
    else:
        sq = int(n**0.5) + 2
        for i in range(3, sq):
            if n % i == 0:
                print(n // i, n - n // i)
                return
        print(1, n - 1)
        return






mode = 'T'

if mode == 'T':
    t = ri()
    for i in range(t):
        solve()
else:
    solve()


import sys
from collections import deque
import heapq

input = lambda: sys.stdin.readline().strip()
ipnut = input
pprint = lambda x: print(' '.join(map(lambda t: str(t + 1), x)))


def mex():
    used = set(a)
    for i in range(n + 1):
        if i not in used:
            return i


for _ in range(int(input())):
    n = int(input())
    f = False
    for i in range(int(n ** 0.5)):
        i += 2
        if n % i == 0:
            print(n // i, n - n // i)
            f = True
            break
    if f:
        pass
    else:
        print(1, n - 1)
    # n, m = map(int, input().split())
    # a = list(map(int, input().split()))


for _ in range(int(input())):
    #n, m = map(int, input().split())
    #A = list(map(int, input().split()))
    n = int(input())
    if n > 3:
        for i in range(2, int(n ** 0.5) + 1):
            if n % i == 0:
                break

        if n % i == 0:
            print(n // i, n -  (n // i))
        else:
            print(1, n - 1)
    else:
        print(1, n - 1)


tt = int(input())

for loop in range(tt):

    n = int(input())

    x = 2
    while x ** 2 <= n:
        if n % x == 0:
            break
        x += 1
    else:
        print(1,n-1)
        continue

    print(n // x , n - n // x)


import math
t = int(input())

for _ in range(t):
    n = int(input())
    ans= False
    for i in range(2, int(math.sqrt(n) +1)):
        if n % i == 0:
            print(str(n//i) + ' ' + str(n - n//i))
            ans = True
            break
    if not ans:
        print('1 ' +  str(n-1))


import sys
input=sys.stdin.readline
t=int(input())
for _ in range(t):
    n=int(input())
    flag=0
    for i in range(2,int(n**.5)+1):
        if(n%i==0):
            print(n//i,(i-1)*n//i)
            flag=1
            break
    if(flag==0):
        print(n-1,1)
            
            
        



T = int(input())

def spf(n):
  for i in range(2,int(n**0.5)+2):
    if n%i == 0:
      return i
  return n

for i in range(T):
  n = int(input())
  #n,m = map(int, input().split())
  #a,b = map(int, input().split())
  #a = list(map(int,input().split()))
  #a = list(input())
  s = spf(n)
  print(n//s,(s-1)*n//s)


from math import *
from collections import *
from bisect import *
import sys
input=sys.stdin.readline
t=int(input())
while(t):
    t-=1
    n=int(input())
    fac=set()
    for i in range(2,int(pow(n,0.5))+1):
        if(n%i==0):
            fac.add(i)
            fac.add(n//i)
    fac.add(1)
    #fac.add(n)
    lcm=float('inf')
    a,b=0,0
    for i in fac:
        if(((i*(n-i))//gcd(i,n-i))<lcm):
            lcm=(i*(n-i))//gcd(i,n-i)
            a,b=i,n-i
    print(a,b)
    
        
            
    
    
    
        
            


from math import *
from sys import *
input = stdin.readline

for _ in range(int(input())):
    
    n = int(input())
    g = -1
    
    for i in range(2,int(sqrt(n))+1):
        if(n%i == 0):
            g = i
            break
    
    if(g == -1):
        print(n-1,1)
        continue
    
    a = n//g
    b = (n//g)*(g-1)
    
    print(a,b)

import sys
input = sys.stdin.readline
I = lambda : list(map(int,input().split()))

t,=I()
for _ in range(t):
	n,=I()
	a=b=0
	for i in range(2,int(n**0.5)+1):
		if n%i==0:
			a=n//i;b=n//i*(i-1)
			break
	if a==0:
		a=1;b=n-1
	print(a,b)