Spring has come, and the management of the AvtoBus bus fleet has given the order to replace winter tires with summer tires on all buses.

You own a small bus service business and you have just received an order to replace $n$ tires. You know that the bus fleet owns two types of buses: with two axles (these buses have $4$ wheels) and with three axles (these buses have $6$ wheels).

You don't know how many buses of which type the AvtoBus bus fleet owns, so you wonder how many buses the fleet might have. You have to determine the minimum and the maximum number of buses that can be in the fleet if you know that the total number of wheels for all buses is $n$.


-----Input-----

The first line contains an integer $t$ ($1 \le t \le 1000$) — the number of test cases. The following lines contain description of test cases.

The only line of each test case contains one integer $n$ ($1 \le n \le 10^{18}$) — the total number of wheels for all buses.


-----Output-----

For each test case print the answer in a single line using the following format.

Print two integers $x$ and $y$ ($1 \le x \le y$) — the minimum and the maximum possible number of buses that can be in the bus fleet.

If there is no suitable number of buses for the given $n$, print the number $-1$ as the answer.


-----Examples-----

Input
4
4
7
24
998244353998244352
Output
1 1
-1
4 6
166374058999707392 249561088499561088


-----Note-----

In the first test case the total number of wheels is $4$. It means that there is the only one bus with two axles in the bus fleet.

In the second test case it's easy to show that there is no suitable number of buses with $7$ wheels in total.

In the third test case the total number of wheels is $24$. The following options are possible:

Four buses with three axles.

Three buses with two axles and two buses with three axles.

Six buses with two axles.

So the minimum number of buses is $4$ and the maximum number of buses is $6$.

Difficulty: EASY
Tags: Number theory

Complete search

Mathematics

Greedy algorithms
Skill types: Complete search

Greedy algorithms

Starter code:

Solutions:
from sys import stdin

def ii():
	return int(stdin.readline())

def mi():
	return map(int, stdin.readline().split())

def li():
	return list(mi())

def si():
	return stdin.readline()
t = 1
t = ii()
for _ in range(t):
	n = ii()
	if n < 4 or n & 1:
		print(-1)
		continue
	print((n + 5) // 6, n // 4)


t = int(input())
for i in range(t):
	n = int(input())
	if n % 2 != 0 or n < 4:
		print(-1)
	else:
		print((n + 4) // 6, n // 4)


import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	(a, b) = (0, 0)
	if n % 2 or n <= 2:
		print(-1)
	else:
		if n % 4 == 0:
			a = n // 4
		else:
			t = n
			while t % 4:
				a += 1
				t -= 6
			a += t // 4
		if n % 6 == 0:
			b = n // 6
		else:
			t = n
			while t % 6:
				b += 1
				t -= 4
			b += t // 6
		print(b, a)
for __ in range(int(input())):
	solve()


import sys
input = sys.stdin.readline

def solve(N):
	if N % 2 == 1:
		print(-1)
		return
	if N < 4:
		print(-1)
		return
	if N % 6 == 0:
		(a, b) = (0, N // 6)
	elif N % 6 == 2:
		a = 2
		b = (N - 8) // 6
	elif N % 6 == 4:
		a = 1
		b = (N - 4) // 6
	min_fleet = a + b
	if N % 4 == 0:
		a = N // 4
		b = 0
	elif N % 4 == 2:
		a = (N - 6) // 4
		b = 1
	max_fleet = a + b
	print(min_fleet, max_fleet)
T = int(input())
for _ in range(T):
	N = int(input())
	solve(N)


tests = int(input())
for _ in range(tests):
	num = int(input())
	rem6 = num % 6
	if num < 4 or num % 2 == 1:
		print(-1)
	else:
		max = num // 4
		min = num // 6 + (1 if rem6 > 0 else 0)
		print(f'{min} {max}')


t = int(input())
for _ in range(t):
	n = int(input())
	t = n // 6
	e = n // 4
	if n < 4:
		print(-1)
		continue
	if n % 4 % 2:
		print(-1)
		continue
	maxx = n // 4
	minn = n // 6
	if n % 6:
		minn += 1
	print(minn, maxx)


n = int(input())
l = []
for i in range(n):
	t = int(input())
	l.append(t)
for i in l:
	max = 0
	min = 0
	s = 0
	if i % 2 != 0 or i < 4:
		print(-1)
		s = 1
	if s == 0:
		max = i // 4
		if i % 6 == 0:
			min = i // 6
		else:
			min = i // 6 + 1
		print(min, max)


t = int(input())
for _ in range(t):
	n = int(input())
	if n % 2:
		print(-1)
	else:
		n = n // 2
		if n < 2:
			print(-1)
			continue
		rem = n % 3
		mn = n // 3 + (0 if rem == 0 else 1)
		mx = n // 2
		print(mn, mx)


for _ in range(int(input())):
	n = int(input())
	if n % 6 == 0:
		wmin = n // 6
	elif n % 6 == 2:
		wmin = max((n - 8) // 6 + 2, 0)
	elif n % 6 == 4:
		wmin = max((n - 4) // 6 + 1, 0)
	else:
		wmin = 0
	if n % 4 == 0:
		wmax = n // 4
	elif n % 4 == 2:
		wmax = max((n - 6) // 4 + 1, 0)
	else:
		wmax = 0
	if wmin * wmax:
		print(wmin, wmax)
	else:
		print(-1)


for _ in range(int(input())):
	n = int(input())
	if n <= 3:
		print(-1)
	elif n & 1 != 0:
		print(-1)
	else:
		a = n
		c = 0
		while a % 6 != 0:
			a = a - 4
			c += 1
		k = a // 6
		mx = c + k
		b = n
		c1 = 0
		while b % 4 != 0:
			b = b - 6
			c1 += 1
		k = b // 4
		mn = c1 + k
		if mn == 0 or mx == 0:
			var = max(mn, mx)
			print(var, var)
		else:
			print(mx, mn)


def minimum(n):
	s = 0
	while n % 6 != 0:
		n -= 4
		s += 1
	return s + n // 6

def maximum(n):
	x = 0
	while n % 4 != 0:
		n -= 6
		x += 1
	return x + n // 4
for _ in range(int(input())):
	n = int(input())
	if n < 4 or n % 2 != 0:
		print(-1)
	else:
		print(f'{minimum(n)} {maximum(n)}')


def calculator(n):
	sol = []
	if n % 2 or n < 4:
		return -1
	n4 = n % 4
	n6 = n % 6
	if n6 == 0:
		sol.append(n // 6)
	else:
		sol.append(n // 6 + 1)
	sol.append(n // 4)
	return sol
t = int(input())
arr = []
for i in range(t):
	arr.append(int(input()))
for i in arr:
	val = calculator(i)
	if val == -1:
		print(val)
	else:
		print(val[0], val[1])


for _ in range(int(input())):
	n = int(input())
	if n % 2 == 1 or n < 4:
		print(-1)
		continue
	if n % 6 == 0:
		min_ans = n // 6
	else:
		assert n % 6 == 2 or n % 6 == 4
		min_ans = n // 6 + 1
	assert n % 4 == 0 or n % 4 == 2
	max_ans = n // 4
	print(min_ans, max_ans)


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


for i in range(int(input())):
	tyre = int(input())
	if tyre <= 3:
		print(-1)
	elif tyre & 1 != 0:
		print(-1)
	else:
		n4 = 0
		n6 = 0
		c4 = 0
		c6 = 0
		tyretemp = tyre
		while tyre % 6 != 0:
			tyre -= 4
			c4 += 1
		n6 = tyre // 6
		tyre = tyretemp
		while tyre % 4 != 0:
			tyre -= 6
			c6 += 1
		n4 = tyre // 4
		n4 = n4 + c6
		n6 = n6 + c4
		if n4 == 0 or n6 == 0:
			temp = max(n4, n6)
			print(temp, temp)
		else:
			print(n6, n4)


t = int(input())
for _ in range(t):
	n = int(input())
	i = 0
	min_cnt = 0
	max_cnt = 0
	if n % 2 != 0:
		print(-1)
	elif n == 4:
		print(1, 1)
	elif n == 6:
		print(1, 1)
	elif n < 4:
		print(-1)
	elif n % 4 == 0:
		if n % 6 == 0:
			print(n // 6, n // 4)
		else:
			print(n // 6 + 1, n // 4)
	elif n % 6 == 0:
		print(n // 6, n // 4)
	else:
		print(n // 6 + 1, n // 4)


for _ in range(int(input())):
	k = int(input())
	if k & 1 or k < 4:
		print(-1)
	else:
		k //= 2
		print((k + 2) // 3, k // 2, sep=' ')


import math
for _ in range(int(input())):
	n = int(input())
	if n % 2 == 1 or n == 2:
		print(-1)
	else:
		temp = n // 4
		tempmin = n // 6 if n % 6 == 0 else n // 6 + 1
		print(tempmin, temp)


for i in range(int(input())):
	a = int(input())
	if a % 2 == 0 and a != 2:
		print(a // 6 + int(a % 6 != 0), a // 4)
	else:
		print(-1)


t = int(input())
for _ in range(t):
	n = int(input())
	a = n // 4
	b = n // 6
	if n % 2 != 0 or n < 4:
		print(-1)
	else:
		print((n + 4) // 6, n // 4)


T = int(input())
for i in range(T):
	a = int(input())
	if a % 4 == 0 or a % 6 == 0 or (a % 4 == 2 and a // 4 >= 1) or (a % 6 == 2 and a // 6 >= 1) or (a % 6 == 4):
		(x, y, z) = (a // 4, a // 6, a % 6)
		if z == 4 or z == 2:
			y += 1
		print(y, x)
	else:
		print('-1')


test_cases = int(input(''))
tests_list = []
for _ in range(0, test_cases):
	no_of_tyres = int(input(''))
	tests_list.append(no_of_tyres)
for no_of_tyres in tests_list:
	if no_of_tyres < 4 or no_of_tyres % 2 != 0:
		print(-1)
	else:
		if no_of_tyres % 6 == 0:
			minimum = no_of_tyres // 6
		else:
			minimum = no_of_tyres // 6 + 1
		maximum = no_of_tyres // 4
		print(f'{minimum} {maximum}')


y = int(input())
for x in range(y):
	n = int(input())
	minn = 0
	maxx = 0
	if n % 2 != 0 or n < 4:
		print(-1)
	else:
		if n % 4 == 0 and n % 6 == 0:
			maxx = n // 4
			minn = n // 6
		elif n % 4 == 0 and n % 6 != 0:
			maxx = n // 4
			tmp = n % 6
			f = 0
			while n % 6 != 0:
				n = n - 4
				f += 1
			minn = n // 6 + f
		elif n % 6 == 0 and n % 4 != 0:
			minn = n // 6
			s = 0
			while n % 4 != 0:
				n = n - 6
				s += 1
			maxx = n // 4 + s
		else:
			s = 0
			f = 0
			m = n
			while n % 4 != 0:
				n = n - 6
				s += 1
			maxx = n // 4 + s
			n = m
			while n % 6 != 0:
				n = n - 4
				f += 1
			minn = n // 6 + f
		print(minn, maxx)


t = int(input())
for i in range(1, t + 1):
	n = int(input())
	if n % 2 == 1 or n <= 3:
		print(-1)
	else:
		minn = n // 6
		maxx = n // 4
		if n % 6 != 0:
			minn += 1
		print(minn, end=' ')
		print(maxx)


t = int(input())
res = []
for _ in range(t):
	n = int(input())
	if n % 2 != 0 or n < 4:
		res.append(-1)
	else:
		if n % 6 == 0:
			nmin = n // 6
		else:
			nmin = n // 6 + 1
		nmax = n // 4
		res.append((nmin, nmax))
for i in range(len(res)):
	if res[i] == -1:
		print(res[i])
	else:
		a = str(res[i][0])
		b = str(res[i][1])
		print(a, b)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	if n % 2 != 0 or n == 2:
		print(-1)
	else:
		c = 0
		k = n
		while n:
			if n % 6 != 0:
				n -= 4
				c += 1
			else:
				c += n // 6
				break
		d = 0
		while k:
			if k % 4 != 0:
				k -= 6
				d += 1
			else:
				d += k // 4
				break
		print(c, d)


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

	def solve(n):
		if n % 2 or n <= 3:
			return [-1]
		k = n // 2
		(maxi, mini) = (0, 0)
		if k % 3 == 0:
			mini = k // 3
		else:
			mini = k // 3 + 1
		maxi = k // 2
		return [mini, maxi]
	print(*solve(n))


for i in range(int(input())):
	a = int(input())
	if a % 2 != 0 or a < 4:
		print(-1)
	elif a % 4 == 0 and a % 6 != 0:
		print(a // 6 + 1, a // 4)
	elif a % 4 != 0 and a % 6 == 0:
		if a % 6 > 3:
			print(a // 6 + 1, a // 4)
		else:
			print(a // 6, a // 4)
	elif a % 4 == 0 and a % 6 == 0:
		print(a // 6, a // 4)
	else:
		print(a // 6 + 1, a // 4)


from math import ceil
for _ in range(int(input())):
	n = int(input())
	if n & 1 or n == 2:
		print(-1)
		continue
	print([n // 6 + 1, n // 6][n % 6 == 0], n // 4)


q = int(input())
for i in range(q):
	n = int(input())
	if n % 2 == 1 or n == 2:
		print(-1)
		continue
	if n % 6 == 0:
		a = n // 6
	elif n % 6 == 2:
		a = (n - 8) // 6 + 2
	else:
		a = (n - 4) // 6 + 1
	if n % 4 == 0:
		b = n // 4
	else:
		b = (n - 6) // 4 + 1
	print(a, b)


for _ in range(int(input())):
	n = int(input())
	print(*[[(n + 5) // 6, n // 4], [-1]][n % 2 | (n < 4)])


for n in [*map(int, open(0))][1:]:
	print(*((0 - -n // 6, n // 4), [-1])[n % 2 or n < 3])


t = int(input())
for z in range(t):
	n = int(input())
	if n < 4 or n % 2 == 1:
		print('-1')
	else:
		p = 0
		if n % 6 == 0:
			p = n // 6
		elif n % 6 != 0:
			p = n // 6 + 1
		print(p, n // 4)


def run():
	n = int(input())
	if n % 2 == 1:
		print(-1)
		return
	n //= 2
	maximum = 0
	if n % 2 == 1 and n - 3 < 0:
		print(-1)
		return
	maximum = n // 2
	minimum = 0
	while n % 3 != 0:
		n -= 2
		minimum += 1
	if n < 0:
		print(-1)
		return
	minimum += n // 3
	print(minimum, maximum)

def main():
	n = int(input())
	for i in range(n):
		run()
main()


import math

def main():
	total = int(input())
	if total % 2 != 0 or total < 4:
		print(-1)
		return
	total = total // 2
	max_count = 0
	min_count = math.inf
	if total % 2 == 0:
		max_count = total // 2
	else:
		max_count = (total - 3) // 2 + 1
	if total % 3 == 0:
		min_count = total // 3
	elif total % 3 == 1:
		min_count = (total - 4) // 3 + 2
	else:
		min_count = (total - 2) // 3 + 1
	print(min_count, max_count, sep=' ')
count = int(input())
for i in range(count):
	main()


for i in range(int(input())):
	n = int(input())
	if n % 2 != 0 or n == 2:
		print(-1)
	else:
		minimum = n // 6
		maximum = n // 4
		if minimum * 6 != n:
			minimum += 1
		print(minimum, maximum)


def solve():
	n = int(input())
	if n % 2 or n == 2:
		print(-1)
		return
	n //= 2
	if n % 2 == 0:
		ans1 = n // 2
		ans2 = n // 6 * 2 + n % 6 // 2
	else:
		ans1 = 1 + (n - 3) // 2
		ans2 = 1
		n -= 3
		ans2 += n // 6 * 2 + n % 6 // 2
	print(ans2, ans1)
for _ in range(int(input())):
	solve()


for _ in range(int(input())):
	n = int(input())
	if n % 2 != 0 or n < 4:
		print(-1)
	else:
		mx = n // 4
		if n % 6 == 0:
			mn = n // 6
		else:
			mn = n // 6 + 1
		print(mn, mx)


def solution(wheel):
	if wheel % 2 == 1 or wheel < 4:
		print(-1)
		return
	if wheel == 4:
		print(1, 1)
		return
	md6 = wheel % 6
	mx = wheel // 4
	mn = 0
	if md6 == 0:
		mn = wheel // 6
	else:
		mn = wheel // 6 + 1
	print(int(mn), int(mx))
tc = int(input())
for i in range(tc):
	wh = int(input())
	solution(wh)


def f(n):
	if n % 2 == 1 or n < 4:
		return -1
	else:
		cand = []
		if n // 2 % 2 == 1 and n > 6:
			cand.append((n - 6) // 4 + 1)
		if n // 2 % 2 == 0:
			cand.append(n // 4)
		if n % 3 == 0 and n >= 6:
			cand.append(n // 6)
		if n % 3 == 1 and n > 4:
			cand.append((n - 4) // 6 + 1)
		if n % 3 == 2 and n > 8:
			cand.append((n - 8) // 6 + 2)
	return (min(cand), max(cand))
n = int(input())
ret_list = []
for _ in range(n):
	x = int(input())
	ret_list.append(f(x))
for v in ret_list:
	if v == -1:
		print(-1)
	else:
		print(v[0], v[1])


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


for _ in range(int(input())):
	num = int(input())
	lst = []
	if num % 2 or num < 4:
		lst.append(-1)
	elif num % 4 == num % 6 == 0:
		lst.append(num // 4)
		lst.append(num // 6)
	elif num % 6 == 0:
		lst.append(1 + (num - 6) // 4)
		lst.append(num // 6)
	elif num % 4 == 0:
		lst.append(num // 4)
		if (num - 4) % 6 == 0:
			lst.append(1 + (num - 4) // 6)
		else:
			lst.append(2 + (num - 8) // 6)
	else:
		lst.append(1 + (num - 6) // 4)
		if (num - 4) % 6 == 0:
			lst.append(1 + (num - 4) // 6)
		else:
			lst.append(2 + (num - 8) // 6)
	lst.sort()
	print(*lst)


t = int(input())
for i in range(t):
	n = int(input())
	if n < 4:
		print(-1)
	elif n % 2 != 0:
		print(-1)
	else:
		print(n // 6 + int(n % 6 != 0), end=' ')
		print(n // 4)


t = int(input())
for _ in range(t):
	n = int(input())
	if n % 2 == 0 and n // 2 > 1:
		mini = n // 6 if n % 6 == 0 else n // 6 + 1
		maxi = n // 4
		if mini == 0:
			mini = 1
		print(mini, maxi)
	else:
		print(-1)


for _ in range(int(input())):
	n = int(input())
	if n % 2 == 1 or n < 4:
		print(-1)
	else:
		max = n // 4
		if n % 6 == 0:
			min = n // 6
		else:
			min = n // 6 + 1
		print(min, max)


for _ in range(int(input())):
	n = int(input())
	if n % 2 == 1 or n < 4:
		print(-1)
	else:
		mini = n // 6
		rem = n % 6
		if rem > 0:
			mini += 1
		maxi = n // 4
		print(mini, maxi)


def solution(content):
	if content < 4 or content % 2 != 0:
		print(-1)
		return
	remain = content % 6
	if remain == 0:
		mini = content // 6
	else:
		mini = content // 6 + 1
	maxi = content // 4
	print(mini, maxi)
t = int(input())
for i in range(t):
	content = int(input())
	solution(content)


t = int(input())
while t > 0:
	n = int(input())
	r = n % 4
	fl = 1
	if r == 0:
		ma = n // 4
	elif r == 2:
		ma = 1 + (n - 6) // 4
	else:
		fl = -1
	r = n % 6
	if r == 0:
		mi = n // 6
	elif r == 2:
		mi = 2 + (n - 8) // 6
	elif r == 4:
		mi = 1 + (n - 4) // 6
	else:
		fl = -1
	if fl == -1 or n < 4:
		print('-1')
	else:
		print(mi, ma)
	t -= 1


t = int(input())
for vvod in range(t):
	n = int(input())
	if n % 2 != 0:
		print('-1')
		continue
	if n == 2:
		print('-1')
		continue
	if n % 6 == 0:
		x = n // 6
	else:
		x = n // 6 + 1
	y = n // 4
	print(x, y)


t = int(input())
for _ in range(t):
	n = int(input())
	if n % 2 == 1 or n <= 3:
		print(-1)
	else:
		tMax = n // 4
		remain = n % 4
		tMin = n // 6
		if n % 6 == 2 or n % 6 == 4:
			tMin += 1
		print(tMin, tMax)


t = int(input())
for asdfghjkl in range(t):
	n = int(input())
	if n % 2 != 0:
		print(-1)
	else:
		a = n // 4
		b = n // 6
		if n % 6 == 2 and n >= 4:
			b += 1
		elif n % 6 == 4:
			b += 1
		if b == 0 and a == 0:
			print(-1)
		else:
			print(b, a)


n = int(input())
for _ in range(n):
	k = int(input())
	if k % 2 != 0 or k < 4:
		print(-1)
	else:
		(xmin, xmax) = (0, 0)
		if k % 4 == 2:
			xmin = 1 + (k - 6) // 4
		else:
			xmin = k // 4
		if k % 6 == 2:
			xmax = 2 + (k - 8) // 6
		elif k % 6 == 4:
			xmax = 1 + (k - 4) // 6
		else:
			xmax = k // 6
		print(xmax, xmin)


tc = int(input())
for i in range(tc):
	x = int(input())
	if x % 2 == 1 or x < 4:
		print(-1)
	else:
		if x % 6 == 0:
			min1 = x // 6
		elif x % 6 == 2:
			min1 = (x - 8) // 6 + 2
		elif x % 6 == 4:
			min1 = (x - 4) // 6 + 1
		if x % 4 == 0:
			max1 = x // 4
		elif x % 4 == 2:
			max1 = (x - 6) // 4 + 1
		print(min1, max1)


t = int(input())
for i in range(t):
	n = int(input())
	if n % 2 != 0:
		print(-1)
	else:
		mi = 0
		r6 = n % 6
		if r6 == 0:
			mi += n // 6
		elif r6 == 2:
			mi += (n - 8) // 6 + 2
		elif r6 == 4:
			mi += (n - 4) // 6 + 1
		r4 = n % 4
		ma = 0
		if r4 == 0:
			ma += n // 4
		elif r4 == 2:
			ma += (n - 6) // 4 + 1
		if n < 4:
			print(-1)
		else:
			print(mi, ma)


for _ in range(int(input())):
	n = int(input())
	if n % 2 or n < 4:
		print(-1)
	else:
		if n % 4 == 0 or n % 4 == 2:
			maxx = n // 4
		if n % 6 == 0:
			minn = n // 6
		elif n % 6 == 2 or n % 6 == 4:
			minn = n // 6 + 1
		print(minn, maxx)


from bisect import bisect_left
for _ in range(int(input())):
	n = int(input())
	if n == 4:
		print(1, 1)
	elif n % 2 != 0 or n < 4:
		print(-1)
	else:
		ma = n // 4
		r = n % 4
		mi = n // 6
		r = n % 6
		if r == 4:
			mi += 1
		elif r == 2:
			mi += 1
		print(mi, ma)


t = int(input())
for i in range(t):
	n = int(input())
	if n % 2 != 0 or n == 2:
		print(-1)
	elif n % 6 == 0 and n % 4 == 0:
		print(n // 6, n // 4)
	elif n % 4 == 0 and n % 6 == 4:
		print(n // 6 + 1, n // 4)
	elif n % 4 == 0 and n % 6 == 2:
		print(n // 6 + 1, n // 4)
	elif n % 4 == 2 and n % 6 == 0:
		print(n // 6, n // 4)
	elif n % 4 == 2 and n % 6 == 2:
		print(n // 6 + 1, n // 4)
	elif n % 4 == 2 and n % 6 == 4:
		print(n // 6 + 1, n // 4)


import sys

def solve():
	n = int(sys.stdin.readline())
	if n % 2 == 1:
		print(-1)
		return
	n = n // 2
	for i in range(10):
		if n - i * 2 < 0:
			print(-1)
			return
		if (n - i * 2) % 3 == 0:
			m = i + (n - i * 2) // 3
			break
	for i in range(10):
		if n - i * 3 < 0:
			print(-1)
			return
		if (n - i * 3) % 2 == 0:
			M = i + (n - i * 3) // 2
			break
	print(m, M)

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


t = int(input())
for _ in range(t):
	n = int(input())
	if n & 1 or n < 4:
		print(-1)
		continue
	four = n // 4
	mx = four
	if n % 6 == 0:
		print(n // 6, mx)
	elif n % 6 == 4:
		print(n // 6 + 1, mx)
	else:
		print(n // 6 + 1, mx)


def solve():
	n = 0
	n = int(input())
	if n % 2 == 1:
		print('-1')
		return
	n //= 2
	if n < 2:
		print('-1')
		return
	ans1 = n // 2
	mod = n % 3
	if mod != 0:
		ans2 = n // 3 + 1
	else:
		ans2 = n // 3
	print(str(ans2) + ' ' + str(ans1))
T = 0
T = int(input())
for i in range(T):
	solve()


N = int(input())
for _ in range(N):
	n = int(input())
	if n % 2 != 0 or n < 4:
		print(-1)
	else:
		if n % 6 == 0:
			min_cnt = n // 6
		else:
			min_cnt = n // 6 + 1
		max_cnt = n // 4
		print(min_cnt, max_cnt)


for _ in range(int(input())):
	n = int(input())
	if n % 2 == 1:
		print(-1)
	elif n < 4:
		print(-1)
	else:
		x = 0
		y = 0
		if n % 6 == 0:
			x = n // 6
		else:
			x = n // 6 + 1
		y = n // 4
		print(x, y)


for _ in range(int(input())):
	N = int(input())
	if N % 2 or N < 4:
		print(-1)
	elif N < 6:
		print(N // 4, N // 4)
	elif N == 6:
		print(1, 1)
	else:
		X = N % 6 // 4 + N // 6
		if N % 6 % 4 != 0:
			X += 1
		Y = N % 4 // 6 + N // 4
		print(X, Y)


t = int(input())
for i in range(t):
	n = int(input())
	x = n
	g = n
	if n % 2 == 1 or n == 2:
		print('-1')
	else:
		f = g // 4
		if g % 4 == 2:
			f = f - 1
			m = f + 1
		else:
			m = f
		s = x // 6
		if x % 6 == 2:
			mi = s - 1 + 2
		elif x % 6 == 4:
			mi = s + 1
		else:
			mi = s
		print(mi, m)


for i in range(int(input())):
	n = int(input())
	if n % 2 == 1 or n == 2:
		print(-1)
	else:
		if n % 6 == 0:
			x = n // 6
		else:
			x = n // 6 + 1
		y = n // 4
		print(x, y)


t = int(input())
for i in range(t):
	n = int(input())
	if n == 0 or n == 2:
		print(-1)
		continue
	if n % 4 == 1 or n % 4 == 3:
		print(-1)
	else:
		mini = 0
		maxi = 0
		rem = 0
		rem = n % 6
		maxi = n // 4
		if rem > 0:
			mini = n // 6 + 1
		else:
			mini = n // 6
		print(mini, maxi)


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	if n % 2 == 1 or n < 4:
		print(-1)
		continue
	mini = n // 4
	maxi = 0
	if n % 6 == 0:
		maxi = n // 6
	else:
		maxi = n // 6 + 1
	print(maxi, mini)


def main():
	n = int(input())
	if n % 2 == 1 or n < 4:
		print(-1)
		return
	n //= 2
	max_cnt = n // 2
	min_cnt = n // 3
	if n % 3 == 1:
		min_cnt += 1
	if n % 3 == 2:
		min_cnt += 1
	print(min_cnt, max_cnt)
t = 1
t = int(input())
for _ in range(t):
	main()


for i in range(int(input())):
	x = int(input())
	if x % 2 == 1 or x == 2:
		print(-1)
	else:
		u = x % 12
		n = x // 12
		if u == 4:
			print(n * 2 + 1, n * 3 + 1)
		elif u == 6:
			print(n * 2 + 1, n * 3 + 1)
		elif u == 8:
			print(n * 2 + 2, n * 3 + 2)
		elif u == 10:
			print(n * 2 + 2, n * 3 + 2)
		elif u == 0:
			print(n * 2, n * 3)
		elif u == 2:
			print(n * 2 - 1 + 2, n * 3)


t = int(input())
for _ in range(t):
	n = int(input())
	x = n % 4
	if x == 1 or x == 3 or n < 4:
		print(-1)
		continue
	ma = n // 4
	x = n % 6
	mi = n // 6
	if x != 0:
		mi += 1
	print(mi, ma)


N = int(input())
for i in range(N):
	n = int(input())
	if n % 2 or n < 4:
		print(-1)
		continue
	rmi = n // 4
	rmx = n // 6
	mo = n % 6
	if mo == 2 or mo == 4:
		rmx += 1
	print(rmx, rmi)


t = int(input())
for i in range(t):
	n = int(input())
	if n < 4 or n % 2 == 1:
		print(-1)
		continue
	(x, y) = ((n + 4) // 6, n // 4)
	print(x, y)


for _ in range(int(input())):
	n = int(input())
	g = n % 6
	h = n % 4
	fl = True
	if n >= 4:
		if g == 0:
			y = n // 6
		elif g == 2:
			y = n // 6 + 1
		elif g == 4:
			y = n // 6 + 1
		else:
			print(-1)
			fl = False
		if fl:
			if h == 2 or h == 0:
				x = n // 4
			else:
				print(-1)
				fl = False
		if fl:
			print(min(x, y), max(x, y))
	else:
		print(-1)


t = int(input())
for i in range(t):
	n = int(input())
	max = 0
	min = 0
	if n % 2 != 0 or n <= 3:
		print(-1)
		continue
	else:
		max = n // 4
		if n % 6 == 0:
			min = n // 6
		else:
			min = n // 6 + 1
	print(min, max)


def cars(n):
	if n % 2 == 1 or n < 4:
		print(-1)
		return
	n //= 2
	if n % 3 == 0:
		x_min = n // 3
	elif n % 3 == 2:
		x_min = (n - 2) // 3 + 1
	elif n % 3 == 1:
		x_min = (n - 4) // 3 + 2
	if n % 2 == 0:
		x_max = n // 2
	else:
		x_max = (n - 3) // 2 + 1
	print(x_min, x_max)
	return
t = int(input())
for _ in range(t):
	cars(int(input()))


for _ in range(int(input())):
	n = int(input())
	if n % 2 == 1 or n < 4:
		print(-1)
	else:
		t1 = n
		t2 = n
		count1 = 0
		count2 = 0
		while t1 % 4 != 0:
			t1 -= 6
			count1 += 1
		maxi = t1 // 4 + count1
		while t2 % 6 != 0:
			t2 -= 4
			count2 += 1
		mini = t2 // 6 + count2
		print(min(mini, maxi), max(mini, maxi))


for i in range(int(input())):
	n = int(input())
	if n % 2 != 0 or n // 2 == 1:
		print(-1)
		continue
	c_6 = n // 6
	c_4 = (n - c_6 * 6) // 4
	minim = c_6 + c_4
	while c_6 * 6 + c_4 * 4 != n:
		c_6 -= 1
		minim -= 1
		while n - c_6 * 6 - c_4 * 4 > 0:
			c_4 += 1
			minim += 1
	print(minim, end=' ')
	c_4 = n // 4
	c_6 = (n - c_4 * 4) // 6
	maxim = c_6 + c_4
	while c_6 * 6 + c_4 * 4 != n:
		c_4 -= 1
		maxim -= 1
		while n - c_6 * 6 - c_4 * 4 > 0:
			c_6 += 1
			maxim += 1
	print(maxim)


t = int(input())
for i in range(t):
	n = int(input())
	if n % 2 != 0:
		print(-1)
	elif n < 4:
		print(-1)
	elif n < 6:
		print(1, 1)
	else:
		a = n % 6
		if a % 4 == 0:
			x = n // 6 + a // 4
		else:
			x = n // 6 - 1 + (a + 6) // 4
		b = n % 4
		if n % 4 == 0:
			y = n // 4
		else:
			y = n // 4 - 1 + (b + 4) // 6
		print(x, y)


t = int(input())
for case in range(t):
	n = int(input())
	if n < 4 or n % 2 == 1:
		print(-1)
		continue
	maximum = n // 4
	if n % 3 == 0:
		minimum = n // 6
	else:
		minimum = n // 6 + 1
	print(minimum, maximum)