You are given an integer $n$.

Find any pair of integers $(x,y)$ ($1\leq x,y\leq n$) such that $x^y\cdot y+y^x\cdot x = n$.


-----Input-----

The first line contains a single integer $t$ ($1\leq t\leq 10^4$) — the number of test cases.

Each test case contains one line with a single integer $n$ ($1\leq n\leq 10^9$).


-----Output-----

For each test case, if possible, print two integers $x$ and $y$ ($1\leq x,y\leq n$). If there are multiple answers, print any.

Otherwise, print $-1$.


-----Examples-----

Input
5
3
7
42
31250
20732790
Output
-1
-1
2 3
5 5
3 13


-----Note-----

In the third test case, $2^3 \cdot 3+3^2 \cdot 2 = 42$, so $(2,3),(3,2)$ will be considered as legal solutions.

In the fourth test case, $5^5 \cdot 5+5^5 \cdot 5 = 31250$, so $(5,5)$ is a legal solution.

Difficulty: EASY
Tags: Mathematics

Constructive algorithms

Starter code:

Solutions:
for n in [*map(int, open(0))][1:]:
	print((f'{n // 2} 1', -1)[n % 2])


import sys
import math
input = sys.stdin.readline
imp = 'IMPOSSIBLE'
t = int(input())
for test in range(t):
	n = int(input())
	if n % 2 == 0:
		print(1, n // 2)
	else:
		print(-1)


import sys
input = sys.stdin.readline
T = int(input())
for _ in range(T):
	n = int(input())
	if n % 2 == 1:
		print(-1)
	else:
		print(1, n // 2)


num_tests = int(input())
nums = []
for i in range(num_tests):
	nums.append(int(input()))
for i in nums:
	if i % 2 != 0:
		print(-1)
		continue
	print(1, int(i / 2))


import sys
for _ in range(int(sys.stdin.readline())):
	s = int(sys.stdin.readline())
	if s % 2 == 1:
		print('-1')
		continue
	print('1', s // 2)


for i in [*open(0)][1:]:
	i = int(i)
	print('-1' if i % 2 else '1 {}'.format(i // 2))


for m in [*map(int, open(0))][1:]:
	print(*[1, -1, m >> 1][m & 1::2])


for k in [*map(int, open(0))][1:]:
	print(*[1, -1, k >> 1][k & 1::2])


import sys
input = sys.stdin.readline
t = int(input())
for i in range(t):
	n = int(input())
	if n % 2 == 1:
		print(-1)
	else:
		print(n // 2, 1)


import sys

def solve():
	n = int(sys.stdin.readline())
	if n % 2 == 1:
		print(-1)
	else:
		print(1, n // 2)

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	x = int(input())
	if x % 2:
		print(-1)
	else:
		print(1, x // 2)


import sys, math, cmath, time
from bisect import bisect_left
start_time = time.time()

def solve():
	n = inp()
	if n % 2 != 0:
		print(-1)
		return
	print(n // 2, 1)

def main():
	testcases = 1
	testcases = inp()
	for each_testcase in range(testcases):
		solve()

def inp():
	return int(input())

def inps():
	return input().split()
ONLINE_JUDGE = __debug__
if ONLINE_JUDGE:
	input = sys.stdin.readline
main()


import sys

def read(func=int):
	return func(sys.stdin.readline().strip())

def read_array(func=int):
	return list(map(func, read(str).split()))
t = read()
for _ in range(t):
	n = read()
	x = 1
	y = n // 2
	if n % 2:
		print(-1)
	else:
		print(x, y)


ans = []
for _ in range(int(input())):
	n = int(input())
	if n % 2 == 1:
		ans.append('-1')
		continue
	ans.append(f'{n // 2} {1}')
print(*ans, sep='\n')


a = []
[a.append(int(input())) for i in range(int(input()))]
[print(1, int(i / 2)) if i % 2 == 0 else print(-1) for i in a]


def find(n):
	if n % 2 == 0:
		print(1, int(n / 2))
	else:
		print(-1)
n = int(input())
w = []
for _ in range(n):
	w.append(int(input()))
for i in range(n):
	find(w[i])


def Solve(n):
	if n % 2 == 1:
		return [-1]
	return (1, n // 2)
t = int(input())
output = []
for i in range(t):
	n = int(input())
	output.append(Solve(n))
for answer in output:
	print(' '.join(map(str, answer)))


t = int(input())
for i in range(t):
	n = int(input())
	x = 1
	if n % 2 == 0:
		print(1, n // 2)
	else:
		print(-1)


def find_pair(n):
	if n % 2 == 0:
		return (1, int(n / 2))
	return (-1, -1)
t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	(x, y) = find_pair(n)
	if x == -1:
		print(-1)
	else:
		print(x, y)


def solve(n):
	if n % 2 == 0:
		return '1' + ' ' + str(int(n / 2))
	else:
		return -1

def main():
	tests = int(input())
	for i in range(tests):
		print(solve(int(input())))
main()


for _ in range(int(input())):
	n = int(input())
	if n % 2 == 1:
		print(-1)
	else:
		print(1, n // 2)


def solve():
	n = int(input())
	if n & 1 == 0:
		print(1, n // 2)
	else:
		print(-1)
for _ in range(int(input())):
	solve()


d = {}
import math
for x in range(1, 32):
	for y in range(1, 32):
		d[x ** y * y + y ** x * x] = [x, y]
for _ in range(int(input())):
	a = int(input())
	if a % 2 == 0:
		print(a // 2, 1)
		continue
	if a not in d:
		print(-1)
	else:
		print(d[a][0], d[a][1])


t = int(input())
for _ in range(t):
	n = int(input())
	if n % 2 == 0:
		X = n / 2
		print(int(X), 1)
	else:
		print(-1)


for i in range(int(input())):
	b = int(input())
	l = []
	if b % 2 != 0:
		print(-1)
	else:
		print(b // 2, 1)


t = int(input())
while t > 0:
	n = int(input())
	if n % 2 == 1:
		print('-1')
	else:
		print(1, n // 2)
	t -= 1


tc = int(input())
for i in range(tc):
	n = int(input())
	if n % 2 == 1:
		print(-1)
	else:
		print(1, int(n / 2))


a = int(input())
for i in range(a):
	n = int(input())
	if n % 2 == 0:
		print(str(1) + ' ' + str(n // 2))
	else:
		print(-1)


for _ in range(int(input())):
	x = int(input())
	print(f'1 {x // 2}' if x % 2 == 0 else -1)


import math
for _ in range(int(input())):
	n = int(input())
	if n % 2 == 0:
		print(n // 2, 1)
	else:
		print(-1)


for i in range(int(input())):
	n = int(input())
	if n == 2:
		print(1, 1)
	elif n % 2 == 0:
		print(1, n // 2)
	else:
		print(-1)


def solve():
	for _ in range(int(input())):
		n = int(input())
		v = list(map(int, input().split()))

def solve1():
	for _ in range(int(input())):
		n = int(input())
		if n % 2 == 0:
			x = n // 2
			print(x, 1)
		else:
			print(-1)
solve1()


from collections import deque
t = int(input())
for _ in range(t):
	n = int(input())
	if n % 2:
		print(-1)
	else:
		print(1, n // 2)


def main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		if n % 2 == 0:
			print(1, n // 2)
		else:
			print(-1)
main()


for t in range(int(input())):
	n = int(input())
	if n % 2 == 1:
		print(-1)
	else:
		print(n // 2, 1)


for i in range(int(input())):
	n = int(input())
	if n % 2 != 0:
		print(-1)
		continue
	print(1, n // 2)


def main():
	n = int(input())
	if n % 2 == 0:
		print(1, n // 2)
		return
	print(-1)
	return
for _ in range(int(input())):
	main()


for aa in range(int(input())):
	n = int(input())
	if n % 2 != 0:
		print(-1)
		continue
	else:
		print(1, n // 2)


for tests in range(int(input())):
	n = int(input())
	if n % 2 == 0:
		y = n // 2
		print(1, y)
	else:
		print(-1)


import heapq
from collections import *
import math

def lcm(a, b):
	return a * b // math.gcd(a, b)

def factorial(n):
	fact = 1
	for i in range(1, n + 1):
		fact = fact * i
		fact %= 1000000007
	return fact

def primeFactors(n):
	ans = []
	while n % 2 == 0:
		ans.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			ans.append(i)
			n = n / i
	if n > 2:
		ans.append(int(n))
	return ans

def solve():
	n = int(input())
	if n % 2 != 0:
		print(-1)
	else:
		print(1, n // 2)
t = int(input())
for _ in range(t):
	solve()


T = int(input())
ans = []
for t in range(T):
	n = int(input())
	if n % 2 == 0:
		print(n // 2, 1)
	else:
		print(-1)


def solve():
	n = int(input())
	for i in range(n):
		k = int(input())
		if k % 2 == 0:
			print(1, k // 2)
		else:
			print(-1)
solve()


def solution(n):
	if n % 2 == 1:
		print(-1)
		return
	print(1, n // 2)
	return
t = int(input())
for _ in range(t):
	n = int(input())
	solution(n)


def solve(n):
	if n % 2 == 1:
		print(-1)
	else:
		print(1, n // 2)
t = int(input())
for test in range(t):
	n = int(input())
	solve(n)


import math
total = int(input())

def cal(a, b):
	return a ** b * b + b ** a * a

def search(num: int) -> str:
	if num % 2 == 0:
		return '{} {}'.format(1, num // 2)
	return '-1'
for i in range(total):
	print(search(int(input())))