Let's denote a m-free matrix as a binary (that is, consisting of only 1's and 0's) matrix such that every square submatrix of size m × m of this matrix contains at least one zero. 

Consider the following problem:

You are given two integers n and m. You have to construct an m-free square matrix of size n × n such that the number of 1's in this matrix is maximum possible. Print the maximum possible number of 1's in such matrix.

You don't have to solve this problem. Instead, you have to construct a few tests for it.

You will be given t numbers x_1, x_2, ..., x_{t}. For every $i \in [ 1, t ]$, find two integers n_{i} and m_{i} (n_{i} ≥ m_{i}) such that the answer for the aforementioned problem is exactly x_{i} if we set n = n_{i} and m = m_{i}.


-----Input-----

The first line contains one integer t (1 ≤ t ≤ 100) — the number of tests you have to construct.

Then t lines follow, i-th line containing one integer x_{i} (0 ≤ x_{i} ≤ 10^9).

Note that in hacks you have to set t = 1.


-----Output-----

For each test you have to construct, output two positive numbers n_{i} and m_{i} (1 ≤ m_{i} ≤ n_{i} ≤ 10^9) such that the maximum number of 1's in a m_{i}-free n_{i} × n_{i} matrix is exactly x_{i}. If there are multiple solutions, you may output any of them; and if this is impossible to construct a test, output a single integer  - 1. 


-----Example-----
Input
3
21
0
1

Output
5 2
1 1
-1

Difficulty: interview

Starter code:

Solutions:
t = int(input())
for k in range(t):
    x = int(input())
    if x == 0:
        print(1, 1)
        continue
    for i in range(1, int(x ** 0.5) + 2):
        if x % i == 0 and (x // i - i) % 2 == 0 and (x // i - (x // i - i) // 2) ** 2 >= x:
            a, b = x // i, i
            y = (a - b) // 2
            n = a - y
            if y == 0:
                continue
            m = n // y
            if n // m != y:
                continue
            print(n, m)            
            break
    else:
        print(-1)

import math
t = int(input())
for _ in range(t):
    suc = False
    x = int(input())
    for n in range(int(x**0.5)+1,int((4*x/3)**0.5)+2):
        if int((n**2-x)**0.5)**2 == n**2-x:
            mm = int((n**2-x)**0.5)
            m = math.floor(n/mm)
            if n**2-(n//m)**2 == x:
                print(n,m)
                suc = True
                break
    if not suc: print(-1)


from math import sqrt,ceil

def func(x,):
	a = int(ceil(sqrt(x)))
	b = int(ceil(sqrt(2*x)))
	for n in range(a,b+1):
		if n == 0:
			return 1,1
		temp = sqrt((n**2 - x))
		if temp%1 != 0 or temp == 0:
			pass
		else:
			m = int(n/temp)
			if int(n/m) == int(temp):
				return n,m
	return -1,-1


t = int(input())
for i in range(t):
	x = int(input())
	n,m = func(x)
	if n == -1:
		print(-1)
	else:
		print(n,m)


import math

def nextsquare(x):
	y = int(math.sqrt(x))
	return ((y+1)*(y+1))



a = input()
for i in range(int(a)):
	k = int(input())
	j = nextsquare(k)
	answer1 = -1
	answer2 = 0
	while (j <= (4 * k / 3) + 1):
		l = j - k
		if not (l == 0):

			if (int(math.sqrt(l)) * int(math.sqrt(l)) == l):
				n = int(math.sqrt(j))
				m = int(math.sqrt(l))
				r = n % m
				m1 = (n - r)/m
				if r < m1:
					answer1 = n
					answer2 = int(m1)
		j =nextsquare(j)
	if answer1 == -1 :
		print(answer1)
	else:
		print(answer1,answer2)


n = int(input())
for x in range(n):
    x = int(input())
    if x == 0:
        print(1, 1)
    else:
        flag = True
        for d in range(1, int(x**0.5)+2):
            if x % d == 0:
                s = x // d
                n = (s + d)//2
                if int(n) != n:
                    continue
                nm = s - n
                if nm <= 0:
                    continue
                m = n//nm
                if (m>0) and (n**2 - (n//m)**2 == x):
                    print(n, m)
                    flag = False
                    break
        if flag:
            print(-1)

n = int(input())
for x in range(n):
    x = int(input())
    if x == 0:
        print(1, 1)
    else:
        flag = True
        for d in range(1, int(x**0.5)+2):
            if x % d == 0:
                s = x // d
                n = (s + d)//2
                if int(n) != n:
                    continue
                nm = s - n
                if nm == 0:
                    continue
                m = n//nm
                if (m>0) and (n**2 - (n//m)**2 == x):
                    print(n, m)
                    flag = False
                    break
        if flag:
            print(-1)

n = int(input())
for x in range(n):
    x = int(input())
    if x == 0:
        print(1, 1)
    else:
        flag = True
        for d in range(1, int(x**0.5)+1):
            if x % d == 0:
                s = x // d
                n = (s + d)//2
                if int(n) != n:
                    continue
                nm = s - n
                if nm <= 0:
                    continue
                m = n//nm
                if (m>0) and (n**2 - (n//m)**2 == x):
                    print(n, m)
                    flag = False
                    break
        if flag:
            print(-1)

n = int(input())
for x in range(n):
    x = int(input())
    if x == 0:
        print(1, 1)
    else:
        flag = True
        for d in range(1, int(x**0.5)+1):
            if x % d == 0:
                s = x // d
                n = (s + d)//2
                if int(n) != n:
                    continue
                nm = s -n
                if nm <= 0:
                    continue
                m = n//nm
                if (m>0) and (n**2 - (n//m)**2 == x):
                    print(n, m)
                    flag = False
                    break
        if flag:
            print(-1)

import time
import itertools

import math

x = 10**9+2



def find_factor(x):
    k = int(math.ceil(math.sqrt(x)))
    if x//k == k:
        k -=1
    for i in range(k,2,-1):
        if not x%i:
            yield i
    yield 1

def find_factor_div2(x):
    k = int((math.ceil(math.sqrt(x))//2)*2)
    if x//k == k:
        k -=2
    for i in range(k, 1, -2):
        if not x%i and not (x//i)%2:
            yield i
    return 0

def _sol_kMn_kPn_for_x(x):

    if x%4 == 0:
        f = find_factor_div2(x)
        if f:
            for k in f:
                yield k, x/k
        return 0
    if x%2 == 0:
        return 0
    f = find_factor(x)
    if f:
        for k in f:

            yield k, x/k
    return 0


def sol_k_n_for_x(x):
    if x < 4:
        if x == 3:
            yield (1, 2)
        elif x == 0:
            yield (1, 1)
        else:
            return 0
        return

    k_n = _sol_kMn_kPn_for_x(x)

    if not k_n:
        return 0
    for _k, _n in k_n:
        n, k =  ((_n - _k)//2, (_k + _n)//2)

        yield n,k


def sol_m_n(x):

    if x == 0:
        return (1, 1)

    kn = sol_k_n_for_x(x)

    if not kn:
        return -1, -1
    for k, n in kn:
        l = math.ceil((n+1)/(k+1))
        r = math.floor((n)/(k))
    #if l == (n+1)/(k+1):
     #   l +=1

        if l <= r:
            return r, n
    return -1,-1


def __starting_point():
    n = int(input())

    for i in range(n):
        q = int(input())
        m, n = sol_m_n(q)
        if m == -1:
            print(-1)
        else:
            print(int(n), int(m))

# 5, 8

__starting_point()

import math

t = int(input())

for rr in range(t):
	oc = int(input())
	fl = False
	if oc != 0:
		for i in range(2,40000):
			sq1 = i
			v1 = sq1*sq1 - oc
			if v1 > 0 and int(math.sqrt(v1))**2 == v1:
				sv1 = int(math.sqrt(v1))
				l = 2
				r = sq1
				while (r-l) > 1:
					mid = int((l+r)/2)
					vc = int(sq1/mid)
					if (sq1*sq1 - vc*vc) > oc:
						r = mid - 1
					else:
						l = mid
				cr = int(sq1/r)
				cl = int(sq1/l)

				if (sq1*sq1 - cr*cr) == oc and r <= sq1:
					fl = True
					st = str(sq1) +' '+ str(r)
					print(st)	
					break 
				elif (sq1*sq1 - cl*cl) == oc and l <= sq1:
					fl = True
					st = str(sq1) +' '+ str(l)
					print(st)
					break

	if not fl:
		if oc == 0:
			print("1 1")
		else:
			print(-1)

from math import *

def calcul(xi):
	n=int(sqrt(xi))+1
	n2=n**2
	while n2<=2*xi and n<=1000000000:
		nsm2=n2-xi
		nsm=sqrt(nsm2)
		if nsm==int(nsm):
			m=n//nsm
			if n2 - (n//m)**2 == xi:
				return n, int(m)
		n+=1
		n2=n**2
	return -1,-1

t=int(input())
for _ in range(t):
	xi=int(input())
	if xi==0:
		print("1 1")
		continue
	n,m=calcul(xi)
	if m==-1:
		print(-1)
	else:
		print(n,m)


from math import sqrt

# import sys
# from io import StringIO
# sys.stdin = StringIO(open(__file__.replace('.py', '.in')).read())

t = int(input())

for _ in range(t):
    n = int(input())

    if n == 0:
        print(1, 1)
        continue

    sq = int(sqrt(n)) + 1
    while sq * sq <= 2 * n:
        zs = sqrt(sq * sq - n)
        if zs.is_integer():
            m = sq // zs
            if sq * sq - (sq // m) ** 2 == n:
                print(sq, int(m))
                break
        sq += 1
    else:
        print(-1)


n = int(input())
for x in range(n):
    x = int(input())
    if x == 0:
        print(1, 1)
    else:
        flag = True
        for d in range(1, int(x**0.5)+2):
            if x % d == 0:
                s = x // d
                n = (s + d)//2
               # if int(n) != n:
                  #  continue
                nm = s - n
                if nm == 0:
                    continue
                m = n//nm
                if (m>0) and (n**2 - (n//m)**2 == x):
                    print(n, m)
                    flag = False
                    break
        if flag:
            print(-1)

from math import ceil
t = int(input())
for _ in range(t):
    x = int(input())
    if x == 1 or x % 4 == 2:
        print(-1)
    elif x == 0:
        print(1,1)
    else:
        z = 0
        for i in range(ceil((x/3)**0.5),ceil(x**0.5)):
            if x % i == 0 and (x//i-i) % 2 == 0:
                n = (i + x//i)//2
                k = (x//i - i)//2
                m = n//k
                if n//m == k:
                    print(n,m)
                    z = 1
                    break
        if z == 0:
            print(-1)



from math import*
def get(x):
    if x==0:
        print(1,1)
        return
    i=1
    while i*i<=x:
        if not(x%i):
            a,b=int(x/i),i
            if(not((a+b)%2)):
                n=int((a+b)/2)
                n_m=int((a-b)/2)
                if n_m:
                    m=int(n/n_m)
                    if(int(n/m)==n_m and m<=n):
                        print(n,m)
                        return
        i+=1
    print(-1)
    return

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

def test(x):
    i=1
    flag=False
    while i**2 < x:
        if x % i==0:
            a,b=i,x//i
            if (a+b)%2==0:
                z=(a+b)//2
                y=b-z
                u=z//y
                if (z//u==y):
                    y=u
                    flag=True
                    break
        i+=1
    if flag:
        print(str(z)+" "+str(y))

    else:
        if x==0:
            print("1 1")
        else:
            print("-1")
n=int(input())
for j in range(n):
    test(int(input()))

    


from math import*

def get(x):

    if x==0:

        print(1,1)

        return

    i=1

    while i*i<=x:

        if not(x%i):

            a,b=int(x/i),i

            if(not((a+b)%2)):

                n=int((a+b)/2)

                n_m=int((a-b)/2)

                if n_m:

                    m=int(n/n_m)

                    if(int(n/m)==n_m and m<=n):

                        print(n,m)

                        return

        i+=1

    print(-1)

    return



n=int(input())

for i in range(n):get(int(input()))



# Made By Mostafa_Khaled


import math
import sys


def main():

    t = int(input())

    for i in range(t):
        ones = int(input())

        if ones == 0:
            print('1 1')
            continue

        gotem = False
        for j in range(1, ones):
            if j * j > ones:
                break
            if ones % j == 0:
                big = ones // j

                if (j + big) % 2 != 0:
                    continue
                else:
                    a = (j + big) // 2
                    b = big - a
                    if b <= 0:
                        continue
                    n = a
                    m = n//b

                    if n//m != b or n < 1 or m < 1 :
                        continue

                    print('%d %d' % (n,m))
                    gotem = True
                    break

        if not gotem:
            print(-1)

def __starting_point():
    main()


__starting_point()

import math 
 
def div(k):
    res = []
    for i in range(1,int(math.sqrt(k))+2):
        if k % i == 0:
            res.append(i)
    return res
            
t = int(input())
for i in range(t):
    x = int(input())
    if x == 0:
        print("1 1")
    elif x == 1:
        print(-1)
    else:    
        flag = False
        di = div(x)
        for d in di:
            a = x // d
            if ((a+d) % 2 == 0) and (a > d):
                n = (a+d)//2
                lower = (a+d) / (a-d+2)
                upper = (a+d) / (a-d)
                if int(lower) < int(upper):
                    m = int(upper)
                    res = [n,m]
                    flag = True
                    break
        if flag == True:
            print(' '.join(map(str, res)))
        else:
            print(-1)


#Bhargey Mehta (Junior)
#DA-IICT, Gandhinagar
import sys, math, queue, bisect
#sys.stdin = open("input.txt", "r")
MOD = 10**9+7
sys.setrecursionlimit(1000000)

N = 50000

for _ in range(int(input())):
    x = int(input())
    found = None
    for i in range(1, N):
        if i*i-x <= 0: continue
        low, high = 1, N-1
        while low <= high:
            mid = (low+high)>>1
            lhs = i*i - (i//mid)*(i//mid)
            if lhs == x:
                found = (i, mid)
                break
            elif lhs < x:
                low = mid+1
            else:
                high = mid-1
        if found is not None:
            break
    if found is None: print(-1)
    else: print(*found)

def main():
	t = int(input())
	for _ in range(t):
		num = int(input())
		if num == 0:
			print(1, 1)
		else:
			ok = False
			div = 1
			while div * div <= num:
				if num % div == 0:
					add = max(num // div, div)
					sub = min(num // div, div)
					if (add + sub) % 2 == 0:
						n = (add + sub) // 2
						num_zeros = (add - sub) // 2
						if num_zeros != 0:
							k =  n // num_zeros
							if n ** 2 - (n // k) ** 2 == num:
								ok = True
								break
				div += 1
			if ok:
				print(n, k)
			else:
				print(-1)


def __starting_point():
	main()

__starting_point()

import math

t = int(input())

for _ in range(t):
    x = int(input())
    
    found = False
    for n in range(int(math.sqrt(x))+1, int(10**4.6)):
        m = n/math.sqrt(n**2-x)
        m1 = math.ceil(m)
        m2 = math.floor(m)
        
        for m in [m1, m2]:
            if n**2-(n//m)**2==x:
                print(n, m)
                found = True
                break
        if found:
            break
    if not found:
        print(-1)            


import sys
import math
lines = sys.stdin.read().splitlines()
lincnt = -1 

def input():
    nonlocal lincnt
    lincnt += 1
    return lines[lincnt]

def solve():
    x = int(input())
    for n in range(max(1,int(math.sqrt(x) - 5)),int(10**4.7)):
        if n ** 2 <= x:
            continue
        m = math.sqrt(n** 2 / (n** 2 - x))
        for k in range(int(m) - 3, int(m) + 3):
            if k < 1:
                continue
            if n ** 2 - (n // k) ** 2 == x:
                print(n,k)
                return
    print(-1)


for _ in range(int(input())):
    solve()