You are given an integer $n$.

Your task is to find two positive (greater than $0$) integers $a$ and $b$ such that $a+b=n$ and the least common multiple (LCM) of $a$ and $b$ is the minimum among all possible values of $a$ and $b$. If there are multiple answers, you can print any of them.


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 100$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($2 \le n \le 10^9$).


-----Output-----

For each test case, print two positive integers $a$ and $b$ — the answer to the problem. If there are multiple answers, you can print any of them.


-----Examples-----

Input
4
2
9
5
10
Output
1 1
3 6
1 4
5 5


-----Note-----

In the second example, there are $8$ possible pairs of $a$ and $b$:

$a = 1$, $b = 8$, $LCM(1, 8) = 8$;

$a = 2$, $b = 7$, $LCM(2, 7) = 14$;

$a = 3$, $b = 6$, $LCM(3, 6) = 6$;

$a = 4$, $b = 5$, $LCM(4, 5) = 20$;

$a = 5$, $b = 4$, $LCM(5, 4) = 20$;

$a = 6$, $b = 3$, $LCM(6, 3) = 6$;

$a = 7$, $b = 2$, $LCM(7, 2) = 14$;

$a = 8$, $b = 1$, $LCM(8, 1) = 8$.

In the third example, there are $5$ possible pairs of $a$ and $b$:

$a = 1$, $b = 4$, $LCM(1, 4) = 4$;

$a = 2$, $b = 3$, $LCM(2, 3) = 6$;

$a = 3$, $b = 2$, $LCM(3, 2) = 6$;

$a = 4$, $b = 1$, $LCM(4, 1) = 4$.

Difficulty: EASY
Tags: Number theory

Mathematics

Starter code:

Solutions:
import math
primes = [2, 3]
for i in range(4, math.ceil(math.sqrt(10 ** 9))):
	isprime = True
	for x in primes:
		if x > math.sqrt(i):
			break
		if i % x == 0:
			isprime = False
			break
	if isprime:
		primes.append(i)
a = [int(input()) for i in range(int(input()))]
for x in a:
	done = True
	for i in primes:
		if i > x / 2:
			break
		if x % i == 0:
			print(x // i, x - x // i)
			done = False
			break
	if done:
		print(1, x - 1)


import math

def ans(n):
	l = []
	if n % 2 == 0:
		return [n // 2, n // 2]
	else:
		a = n // 2
		for i in range(3, int(math.sqrt(n)) + 1, 2):
			if n % i == 0:
				a = n // i
				return [a, n - a]
		return [1, n - 1]
t = int(input())
l = []
for i in range(t):
	n = int(input())
	l.append(ans(n))
for i in range(t):
	print(' '.join(map(str, l[i])))


from math import sqrt
for _ in range(int(input())):
	n = int(input())
	(a, b) = (1, n - 1)
	if n % 2 == 0:
		a = n // 2
		b = a
	else:
		k = int(sqrt(n)) + 1
		lcm = n - 1
		for i in range(3, k, 2):
			if n % i == 0:
				if n - i < lcm:
					lcm = n - i
					a = i
					b = n - a
				if n - n // i < lcm:
					lcm = n - n // i
					a = n // i
					b = n - a
	print(a, ' ', b)


from math import sqrt
tests = int(input())
for test in range(tests):
	n = int(input())
	if n % 2 == 0:
		min_prime_divisor = 2
	else:
		min_prime_divisor = n
		for i in range(3, int(sqrt(n)) + 1, 2):
			if n % i == 0:
				min_prime_divisor = i
				break
	print(f'{int(n / min_prime_divisor)} {int(n - n / min_prime_divisor)}')


def getf(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return n // i
	return 1
for _ in range(int(input())):
	n = int(input())
	x = getf(n)
	print(x, n - x)


import sys
input = sys.stdin.readline
import math

def print_str_line(str):
	sys.stdout.write(str + '\n')

def print_number(number):
	print_str_line(f'{number}')

def ans(n):
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			return [n // i, n - n // i]
	return [1, n - 1]
number_of_test_cases = int(input())
for i in range(number_of_test_cases):
	n = int(input())
	_ans = ans(n)
	print_str_line(' '.join([str(x) for x in _ans]))


import math

def solve(n):
	if n % 2 == 0:
		s = str(n // 2) + ' ' + str(n // 2)
		return s
	x = math.ceil(math.sqrt(n))
	b = n - 1
	for i in range(2, x + 1):
		if n % i == 0:
			a = n // i
			b = n - n // i
			return str(a) + ' ' + str(b)
	a1 = n - b
	return str(a1) + ' ' + str(b)

def test():
	t = int(input())
	for i in range(t):
		n = int(input())
		print(solve(n))
test()


def prime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return n // i
	return 1
for _ in range(int(input())):
	a = int(input())
	b = prime(a)
	print(b, a - b)


def prime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return n // i
	return 1
for _ in range(int(input())):
	p = int(input())
	q = prime(p)
	print(q, p - q)


T = int(input())
for i in range(T):
	n = int(input())

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


import math

def findLcm(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return n // i
	return 1
for i in range(int(input())):
	n = int(input())
	a = findLcm(n)
	print(a, n - a)


def solve(n):
	answer = 1
	for i in range(2, int(n ** 0.5 + 1)):
		if n % i == 0:
			answer = n / i
			break
	print(f'{int(answer)} {int(n - answer)}')
t = int(input())
for i in range(t):
	solve(int(input()))


def solve(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return n // i
	return 1
t = int(input())
for i in range(t):
	l = int(input())
	a = solve(l)
	print(a, l - a, sep=' ')


import math as m

def f(n):
	if n % 2 == 0:
		print(int(n / 2), int(n / 2))
	else:
		z = 0
		for i in range(2, int(m.sqrt(n) + 1)):
			if n % i == 0:
				z = 1
				print(int(n / i * (i - 1)), int(n / i))
				break
		if z == 0:
			print(n - 1, 1)
for t in range(int(input())):
	inp1 = int(input())
	f(inp1)


import math
import sys

def solve():
	input = sys.stdin.readline
	n = int(input())
	if n % 2 == 0:
		print(n // 2, n // 2)
	else:
		for i in range(3, int(math.sqrt(n)) + 1):
			if n % i == 0:
				print(n // i, n - n // i)
				return
		print(1, n - 1)

def main():
	t = int(input())
	for _ in range(t):
		solve()
main()


def compute_lcm(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return n // i
	return 1
t = int(input())
for i in range(t):
	n = int(input())
	a = compute_lcm(n)
	print(a, n - a)


from dataclasses import dataclass
import math
nt = [2, 3]

@dataclass
class MyInput:
	t: int
	test_cases: list

def get_input():
	t = int(input())
	test_cases = []
	for _ in range(t):
		x = int(input())
		test_cases.append((x,))
	return MyInput(t=t, test_cases=test_cases)

def _populate_nt(n):
	for i in range(5, n, 1):
		is_prime = True
		if is_prime:
			nt.append(i)

def resolve(x):
	for i in range(2, int(math.sqrt(x)) + 1):
		if x % i == 0:
			a = int(x / i)
			return f'{a} {x - a}'
	return f'1 {x - 1}'

def main():
	myinput = get_input()
	for i in range(myinput.t):
		x = myinput.test_cases[i]
		print(resolve(x[0]))
	return myinput
main()


def is_prime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return i
	return 1
for _ in range(int(input())):
	n = int(input())
	x = is_prime(n)
	if x == 1:
		print('1', n - 1)
	else:
		print(f'{n // x} {n - n // x}')


import math

def is_prime(n):
	if n % 2 == 0 and n > 2:
		return False
	return all((n % i for i in range(3, int(math.sqrt(n)) + 1, 2)))

def not_Prime_LCM(n):
	for i in range(3, n // 2 + 1, 2):
		if n % i == 0:
			smallest = n - i
			num = n // i
			if n - num < smallest:
				print(num, n - num)
				return
			else:
				print(i, smallest)
				return
		else:
			pass
	return
test_case = int(input())
while test_case != 0:
	n = int(input())
	if n % 2 == 0:
		l = n // 2
		print(l, l)
	elif is_prime(n) == True:
		print(1, n - 1)
	else:
		not_Prime_LCM(n)
	test_case = test_case - 1


from math import sqrt

def main():
	for i in range(0, int(input())):
		minLcm(int(input()))

def minLcm(n):
	largestfac = largest_factor(n)
	print(largestfac, n - largestfac)

def largest_factor(n):
	largest = 0
	for i in range(1, int(sqrt(n)) + 1):
		if n % i == 0:
			factor1 = i
			factor2 = n // i
			if factor1 != n:
				largest = max(largest, factor1)
			if factor2 != n:
				largest = max(largest, factor2)
	return largest
main()


from typing import List
from bisect import *
from collections import *
from functools import *
from itertools import *
from math import *
from queue import PriorityQueue

def main1(n):
	res = []
	mlcm = n - 1
	for i in range(1, n // 2 + 1):
		temp = i * (n - i) / gcd(i, n - i)
		if temp <= mlcm:
			mlcm = temp
			res = [i, n - i]
	print(*res, mlcm)

def main(n):
	if n % 2 == 0:
		print(n // 2, n // 2)
		return
	dst = int(sqrt(n) + 1)
	dst = min(dst, n - 2)
	find = False
	for i in range(2, dst + 1):
		if n % i == 0:
			print(n // i, n - n // i)
			find = True
			break
	if find == False:
		print(1, n - 1)
caseNum = int(input())
for i in range(0, caseNum):
	n = int(input())
	main(n)


for _ in range(int(input())):
	n = int(input())
	for i in range(2, int(n ** 0.5) + 1):
		if not n % i:
			print(n // i, n - n // i)
			break
	else:
		print(1, n - 1)


iter = int(input())
for j in range(iter):
	n = int(input())
	gcd = 1
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			gcd = n // i
			break
	print(gcd, n - gcd)


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


import math
for i in range(int(input())):
	n = int(input())
	if n % 2 == 0:
		print(n // 2, n // 2, sep=' ', end='\n')
	else:
		flag = 0
		for j in range(2, int(math.sqrt(n)) + 1):
			if n % j == 0 and (n - j) % j == 0:
				flag = 1
				if (n - n // j) % (n // j) == 0 and n - n // j:
					print(n // j, n - n // j, sep=' ', end='\n')
					break
				else:
					print(j, n - j, sep=' ', end='\n')
					break
		if flag == 0:
			print(1, n - 1, sep=' ', end='\n')


for _ in range(int(input())):
	n = int(input())
	temp = 1
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			temp = n // i
			break
	print(temp, n - temp)


import sys
for lol in range(int(input())):
	n = int(input())
	for i in range(2, min(int(n ** 0.5) + 2, n - 1)):
		if n % i == 0:
			print((i - 1) * n // i, n // i)
			break
	else:
		print(1, n - 1)


import math
t = int(input())
for _ in range(t):
	k = int(input())
	if k % 2 == 0:
		print(k // 2, k // 2)
		continue
	newK = k
	for i in range(2, math.ceil(math.sqrt(k)) + 1):
		if k % i == 0:
			newK = newK // i
			break
	if k == newK:
		print(1, k - 1)
		continue
	print(newK, k - newK)


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


from math import sqrt
for _ in range(int(input())):
	n = int(input())
	a = 1
	for j in range(2, int(sqrt(n) + 1)):
		if n % j == 0:
			a = n // j
			break
	print(a, n - a)


for i in range(int(input())):
	flag = False
	n = int(input())
	for j in range(2, int(pow(n, 1 / 2)) + 1):
		if n % j == 0:
			print(n // j, (j - 1) * n // j)
			flag = True
			break
	if not flag:
		print(1, n - 1)


import math
t = int(input())
for i in range(t):
	n = int(input())
	m = int(math.sqrt(n))
	flag = 1
	for j in range(2, m + 1):
		if n % j == 0:
			x = n // j
			print(x, end=' ')
			print(n - x)
			flag = 0
			break
	if flag == 1:
		print(1, end=' ')
		print(n - 1)


import math
for _ in range(int(input())):
	n = int(input())
	ans = 1
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			ans = n // i
			break
	print(ans, n - ans)


case = int(input())
for i in range(case):
	n = int(input())
	if n % 2 == 0:
		print(n // 2, n // 2)
		continue
	flag = False
	t = 3
	while t * t <= n:
		if n % t == 0:
			print(n // t, n - n // t)
			flag = True
			break
		t += 2
	if not flag:
		print(1, n - 1)


from math import sqrt

def sieve_of_eratosthenes(n):
	primes = [True] * (n + 1)
	(primes[0], primes[1]) = (False, False)
	for i in range(2, int(sqrt(n)) + 1):
		if primes[i]:
			for j in range(i * i, n + 1, i):
				primes[j] = False
	return primes
primes = sieve_of_eratosthenes(1000000)
for _ in range(int(input())):
	n = int(input())
	if n % 2 == 0:
		print(n // 2, n // 2)
	else:
		for i in range(2, int(sqrt(n)) + 1):
			if primes[i]:
				if n % i == 0:
					a = n // i
					print(a, n - a)
					break
		else:
			print(1, n - 1)


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


import math
t = int(input())
for _ in range(t):
	n = int(input())
	if n == 2:
		print(1, 1)
	elif n == 3:
		print(1, 2)
	else:
		for i in range(2, int(math.sqrt(n) + 1)):
			if n % i == 0:
				print(n // i, n - n // i)
				break
		else:
			print(1, n - 1)


import math
a = [int(input()) for i in range(int(input()))]
for x in a:
	done = True
	for i in range(2, round(math.sqrt(x)) + 1):
		if x % i == 0:
			print(x // i, x - x // i)
			done = False
			break
	if done:
		print(1, x - 1)


import math
t = int(input())
for i in range(t):
	n = int(input())
	flag = True
	for j in range(2, math.floor(math.sqrt(n)) + 1):
		if n % j == 0:
			print(n // j, n - n // j)
			flag = False
			break
	if flag:
		print(1, n - 1)


from math import gcd

def brute(n):
	ans = []
	for i in range(1, n):
		b = n - i
		ans.append((i * b // gcd(i, b), i, b))
	ans.sort()
	print(ans)
t = int(input())
for i in range(t):
	n = int(input())
	best = []
	for i in range(1, int(n ** 0.5) + 1):
		if n % i == 0:
			b = n - i
			a1 = n // i
			b1 = n - a1
			best.append((b * i // gcd(b, i), b, i))
			if a1 == 0 or b1 == 0:
				continue
			best.append((a1 * b1 // gcd(a1, b1), a1, b1))
	got = min(best)
	print(got[1], got[2])


t = int(input())
for i in range(t):
	n = int(input())
	if n % 2 == 0:
		print(n // 2, n // 2)
	elif n % 3 == 0:
		q = n // 3
		d = n - q
		print(q, d)
	elif n % 5 == 0:
		q = n // 5
		d = n - q
		print(q, d)
	elif n % 7 == 0:
		q = n // 7
		d = n - q
		print(q, d)
	elif n % 9 == 0:
		q = n // 9
		d = n - q
		print(q, d)
	else:
		x = []
		for i in range(2, int(n ** 0.5) + 1):
			if n % i == 0:
				x.append(i)
				break
		if x:
			g = n // x[0]
			k = n - g
			if g * k < n - 1:
				print(1, n - 1)
			else:
				print(g, k)
		else:
			print(1, n - 1)


t = int(input())
for test in range(t):
	n = int(input())
	if n % 2 == 0:
		print(n // 2, n // 2)
	else:
		for i in range(3, int(n ** (1 / 2)) + 1):
			if n % i == 0:
				print(n // i, n - n // i)
				break
		else:
			print(1, n - 1)


t = int(input())
while t:
	t -= 1
	n = int(input())
	a = 1
	for g in range(2, int(n ** 0.5) + 1):
		if n % g == 0:
			a = n // g
			break
	print(a, n - a)


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


import math
mod1 = 1000000007
T = int(input())
for test in range(T):
	n = int(input())
	ans = 1
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			ans = n // i
			break
	print(ans, n - ans)


import math
t = int(input())
for _ in range(t):
	n = int(input())
	if n & 1 == 0:
		print(n // 2, n // 2)
	else:
		ans = n
		mx_fct = 1
		for i in range(2, int(n ** (1 / 2)) + 1):
			if n % i == 0:
				mx_fct = max(i, n // i, mx_fct)
		(a, b) = (mx_fct, n - mx_fct)
		print(a, b)


t = int(input())
for tc in range(t):
	n = int(input())
	temp = 1
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			temp = n // i
			break
	print(temp, n - temp)


t = int(input())
for t0 in range(t):
	n = int(input())
	lowest_p = None
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			lowest_p = i
			break
	if lowest_p == None:
		lowest_p = n
	a = int(n / lowest_p)
	b = (lowest_p - 1) * a
	print(a, b)


import math
t = int(input())
for T in range(t):
	n = int(input())
	if n % 2 == 0:
		print(int(n / 2), int(n / 2))
	else:
		ans = n
		up = int(math.sqrt(n)) + 2
		for x in range(2, up):
			if n % x == 0:
				ans = x
				break
		p1 = int(n / ans)
		p2 = int((ans - 1) * (n / ans))
		print(p1, p2)


import math
testCount = int(input())
for i in range(testCount):
	var1 = int(input())
	smallestNum = 1
	for num in range(math.floor(math.sqrt(var1))):
		if var1 % (num + 2) == 0:
			smallestNum = num + 2
			break
	if smallestNum == 1:
		print(str(var1 - 1) + ' 1')
	else:
		print(str(int(var1 / smallestNum)) + ' ' + str(int(var1 - var1 / smallestNum)))


t = int(input())

def solve():
	n = int(input())
	k = 2
	while k * k <= n:
		if n % k == 0:
			print(n // k, n - n // k)
			return
		k += 1
	print(1, n - 1)
while t:
	solve()
	t -= 1


listofnums = list(map(int, [*open(0)][1:]))

def minLCM(n):
	a = 1
	b = 2
	while b * b <= n:
		if n % b == 0:
			a = n // b
			return f'{a} {n - a}'
		b += 1
	return f'{a} {n - a}'
for i in listofnums:
	print(minLCM(i))


from math import gcd

def solve():
	n = int(input())
	(a, i) = (1, 2)
	while i * i <= n:
		if n % i == 0:
			a = n // i
			break
		i += 1
	print(a, n - a)
tt = 1
tt = int(input())
for _ in range(tt):
	solve()


import math
for i in range(int(input())):
	n = int(input())
	a = 0
	b = 0
	for val in range(1, int(math.sqrt(n))):
		if n % (val + 1) == 0:
			a = n // (val + 1)
			b = n - n // (val + 1)
			break
	if a == 0 and b == 0:
		print(1, n - 1)
	else:
		print(a, b)


import math

def pg(x):
	vf = False
	i = 3
	while i <= math.sqrt(x) and vf == False:
		if x % i == 0:
			vf = True
		else:
			i += 2
	if vf == False:
		return 1
	else:
		return x // i
for _ in range(int(input())):
	n = int(input())
	if n % 2 == 0:
		a = n // 2
		b = n // 2
	else:
		a = pg(n)
		b = n - a
	print(a, b)


import math
x = int(input())
for i in range(x):
	a = int(input())
	delitelj = 0
	test = True
	for i in range(2, math.ceil(math.sqrt(a)) + 1):
		if a % i == 0:
			delitelj = i + delitelj
			test = False
			break
	if test == True:
		print(1, int(a - 1))
	if test == False:
		print(int(a - a / delitelj), int(a / delitelj))


from math import sqrt
for i in range(int(input())):
	n = int(input())
	l = int(sqrt(n))
	ind = 2
	while n % ind != 0 and ind <= l:
		ind += 1
	if n % ind == 0:
		print(n // ind, n - n // ind)
	else:
		print(1, n - 1)


def smallestPrimeDivisor(n):
	if n % 2 == 0:
		return 2
	found = False
	i = 3
	while found == False and i <= int(n ** 0.5):
		if n % i == 0:
			return i
		i += 2
	return n
t = int(input())
for i in range(t):
	n = int(input())
	p = smallestPrimeDivisor(n)
	print(str(int((p - 1) * n / p)) + ' ' + str(int(n / p)))


import math

def primeFactors(n):
	l = []
	c = 2
	while n > 1:
		if n % c == 0:
			l.append(c)
			n = n / c
		else:
			c = c + 1
	return l

def prime(n):
	prime_flag = 0
	if n > 1:
		for i in range(2, int(math.sqrt(n)) + 1):
			if n % i == 0:
				prime_flag = 1
				break
	return prime_flag
t = int(input())
while t:
	n = int(input())
	i = 1
	ans = 0
	d = prime(n)
	if n % 2 == 0:
		print(n // 2, end=' ')
		print(n // 2)
	elif d == 0:
		print(1, end=' ')
		print(n - 1)
	else:
		m = 999999999
		k = int(math.sqrt(n))
		for i in range(3, k + 1):
			if n % i == 0:
				m = min(m, i)
		ans = n // m
		ans_1 = n - ans
		print(ans, end=' ')
		print(ans_1)
	t = t - 1


import sys
input = lambda : sys.stdin.readline().strip()
for _ in range(int(input())):
	n = int(input())

	def prime(n):
		for i in range(2, int(n ** 0.5) + 1):
			if n % i == 0:
				return False
		return True
	i = 2
	if prime(n):
		print(1, n - 1)
	else:
		while True:
			if n % i == 0:
				if prime(i):
					print(n // i, n - n // i)
					break
			i += 1


for _ in range(int(input())):
	(n, d) = (int(input()), 2)
	while d * d <= n:
		if n % d == 0:
			print(n // d, (d - 1) * n // d)
			break
		d += 1
	if d * d > n:
		print(n - 1, 1)


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


n = int(input())
for i in range(n):
	s = int(input())
	a = 1
	g = 2
	while g * g <= s:
		if s % g == 0:
			a = s / g
			break
		g += 1
	print(int(a), int(s - a))


t = int(input())
while t > 0:
	n = int(input())
	a = 1
	g = 2
	while g * g <= n:
		if n % g == 0:
			a = n // g
			break
		g += 1
	print(a, n - a)
	t -= 1