Every great chef knows that lucky numbers are positive integers whose decimal representations contain only the lucky digits 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.   

Our chef has recently returned from the Lucky country. He observed that every restaurant in the Lucky country had a lucky number as its name. 
He believes that having a lucky number as a restaurant name can indeed turn out to be very lucky.   

Our chef believes that it is possible to make a lucky number having N digits even luckier. Any number following the rules below is called Lucky lucky number -   
 
1. The number contains only digits 4 and 7. 
2. Count of digit 4 in the number should be divisible by 7. 
3. Count of digit 7 in the number should be divisible by 4.  

Help our chef to compute the count of digit 4 in the smallest Lucky lucky number having N digits. 

------ Input ------ 

First line contains T, number of test cases. Each of the next T lines contains a number N, the number of digits in the Lucky lucky number to be formed.  

1≤T≤1000 
1≤N≤1000000000 (10^{9}) 

------ Output ------ 

If it is not possible to form a Lucky lucky number having N digits, output -1.
Otherwise, output the count of digit 4 in the smallest Lucky lucky number having N digits.

----- Sample Input 1 ------ 
5
7
4
11
1
15
----- Sample Output 1 ------ 
7
0
7
-1
7
----- explanation 1 ------ 
For the last test case, N = 15, the smallest lucky lucky number is
444444477777777. The count of digit 4 is 7.

Difficulty: EASY

Starter code:

Solutions:
for _ in range(int(input())):
	n = int(input())
	count4 = n
	for i in range(n + 2):
		if count4 >= 0:
			if count4 % 7 == 0 and (n - count4) % 4 == 0:
				print(count4)
				break
			else:
				count4 -= 1
		else:
			print('-1')


T = int(input())
for case in range(T):
	n = int(input())
	lucky = 0
	for i in range(7):
		if n - i * 4 < 0:
			break
		if (n - i * 4) % 7 == 0:
			lucky = 1
			print(n - i * 4)
			break
	if not lucky:
		print(-1)


t = int(input())
for _ in range(t):
	n = int(input())
	found = False
	while n >= 0:
		if n % 7 == 0:
			print(n)
			found = True
			break
		n -= 4
	if not found:
		print(-1)


for _ in range(int(input())):
	n = int(input())
	x = n // 7
	flag = 0
	while x >= 0:
		count_4 = x * 7
		count_7 = n - count_4
		if count_4 % 7 == 0 and count_7 % 4 == 0:
			flag = 1
			break
		else:
			x = x - 1
	if flag == 0:
		print(-1)
	else:
		print(count_4)


import math

def find_numbers(x):
	j = 0
	for i in range(0, x + 1):
		j = x - i
		if i % 4 == 0 and j % 7 == 0:
			return j
	return -1
for tc in range(int(input())):
	n = int(input())
	print(find_numbers(n))


def ispossible(n):
	ans = 0
	while n >= 7:
		if n % 7 == 0:
			ans = n
			break
		else:
			n = n - 4
	return ans
t = int(input())
for _ in range(t):
	n = int(input())
	if n % 7 == 0:
		ans = n
	elif ispossible(n - 4):
		ans = ispossible(n - 4)
	elif n % 4 == 0:
		ans = 0
	else:
		ans = -1
	print(ans)


t = int(input())
while t > 0:
	n = int(input())
	k = 0
	if n < 4:
		print(-1)
	elif n < 7:
		print(0)
	else:
		while n > 0:
			r = n % 7
			if r == 0:
				k = n // 7 * 7
				break
			n -= 4
		if k:
			print(k)
		else:
			print(-1)
	t -= 1


t = int(input())
while t:
	n = int(input())
	a = 0
	if n % 7 == 0:
		a = 1
	else:
		for i in range(n // 7, -1, -1):
			if (n - i * 7) % 4 == 0:
				a = 2
				break
	if a == 1:
		print(n)
	elif a == 2:
		print(i * 7)
	else:
		print(-1)
	t -= 1


for _ in range(int(input())):
	n = int(input())
	f = 0
	for i in range(7):
		if n - i * 4 < 0:
			break
		if (n - i * 4) % 7 == 0:
			f = 1
			print(n - i * 4)
			break
	if not f:
		print(-1)


for _ in range(int(input())):
	n = int(input())
	f = 0
	a = n
	while n % 7 != 0:
		n -= 4
	ans = a - n
	if ans % 4 == 0 and n >= 0:
		print(n)
	else:
		print(-1)


t = int(input())
while t != 0:
	t -= 1
	n = int(input())
	n4 = -1
	if n == 4:
		n4 = 0
	elif n < 7:
		pass
	else:
		for i in range(0, n, 4):
			if (n - i) % 7 == 0:
				n4 = n - i
				break
	print(n4)


for i in range(int(input())):
	n = int(input())
	a = 0
	count = 0
	if n % 7 == 0:
		a = 1
	else:
		for j in range(n // 7, -1, -1):
			if (n - j * 7) % 4 == 0:
				count = j
				a = 2
				break
	if a == 1:
		print(n)
	elif a == 2:
		print(count * 7)
	elif a == 0:
		print(-1)


for i in range(int(input())):
	n = int(input())
	while n >= 0:
		if n % 7 == 0:
			print(n)
			break
		n -= 4
	else:
		print(-1)


for _ in range(int(input())):
	n = int(input())
	o = 0
	z = n
	if n % 7 == 0:
		o = 1
		print(n)
	else:
		while z > 0:
			x = z % 7
			z = z - x
			if z % 7 == 0 and (n - z) % 4 == 0:
				print(z)
				o = 1
				break
			else:
				z = z - 7
	if o == 0:
		print(-1)


for _ in range(int(input())):
	s = int(input())
	flag = False
	k = s // 7
	for i in range(0, s // 7 + 1):
		if 7 * k == s:
			flag = True
			break
		elif (s - 7 * k) % 4 == 0:
			flag = True
			break
		else:
			k -= 1
	if flag:
		print(str(7 * k))
	else:
		print(-1)


t = int(input())
for i in range(t):
	n = int(input())
	for j in range(n, -1, -1):
		if j * 4 % 7 == 0 and (n - j) * 7 % 4 == 0:
			print(j)
			break
	else:
		print(-1)


for _ in range(int(input())):
	N = int(input())
	for i in range(N, -1, -1):
		if i * 4 % 7 == 0 and (N - i) * 7 % 4 == 0:
			print(i)
			break
	else:
		print(-1)


def f(n):
	x = n % 7
	return n - 8 if x == 1 else n - 16 if x == 2 else n - 24 if x == 3 else n - 4 if x == 4 else n - 12 if x == 5 else n - 20 if x == 6 else n
t = int(input())
for _ in range(t):
	n = int(input())
	ans = f(n)
	print(ans if ans >= 0 else -1)


try:
	t = int(input())
	for _ in range(t):
		flag = 0
		n = int(input())
		if n % 7 == 0:
			print(n)
			flag = 1
		else:
			while n > 0:
				n = n - 4
				if n % 7 == 0:
					print(n)
					break
					flag = 1
			if n % 7 != 0:
				print(-1)
except Exception:
	pass


t = int(input())
while t != 0:
	n = int(input())
	f = 0
	while f <= n:
		if (n - f) % 7 == 0:
			break
		f += 4
	if f > n:
		print('-1')
	else:
		print(n - f)
	t -= 1


for t in range(int(input())):
	n = int(input())
	b = 0
	while n > 0:
		if n % 7 == 0:
			b += n
			n = 0
		else:
			n -= 4
	if n != 0:
		print(-1)
	else:
		print(b)


for _ in range(int(input())):
	n = int(input())
	k = int(n / 7)
	rem = n % 7
	while k >= 0:
		if rem % 4 == 0:
			print(k * 7)
			break
		else:
			rem += 7
			k -= 1
	else:
		print(-1)


t = int(input())
for _ in range(t):
	N = int(input())
	if N % 7 == 0 and N % 4 != 0:
		print(N)
	elif N < 11 and N % 4 != 0 and (N % 7 != 0):
		print(-1)
	else:
		while N % 7 != 0:
			N = N - 4
		print(N)


t = int(input())
for _ in range(t):
	n = int(input())
	fours = -1
	(four_groups, mod) = divmod(n, 7)
	if mod % 4 != 0:
		for groups in range(four_groups, -1, -1):
			if (n - groups * 7) % 4 == 0:
				fours = groups * 7
				break
	else:
		fours = four_groups * 7
	if fours == -1 and n % 4 == 0:
		fours = 0
	print(fours)


for _ in range(int(input())):
	n = int(input())
	fours = n // 7
	while fours != 0:
		if (n - fours * 7) % 4 == 0:
			print(fours * 7)
			break
		fours -= 1
	else:
		if n % 4 == 0:
			print(0)
		else:
			print(-1)


for i in range(int(input())):
	n = int(input())
	if n % 7 == 0 and n % 4 != 0:
		print(n)
	elif n < 11 and n % 4 != 0 and (n % 7 != 0):
		print(-1)
	else:
		while n % 7 != 0:
			n = n - 4
		print(n)


for i in range(int(input())):
	n = int(input())
	flag = 0
	for i in range(n // 4 + 1):
		if (n - 4 * i) % 7 == 0:
			print(n - 4 * i)
			flag = 1
			break
	if flag == 0:
		print('-1')


for _ in range(int(input())):
	n = int(input())
	if n % 7 == 0:
		print(n)
		continue
	while n > 0:
		n -= 4
		if n % 7 == 0:
			print(n)
			break
	if n % 7 != 0:
		print(-1)


v = int(input())
for vi in range(v):
	n = int(input())
	if n < 7 and n != 4:
		print(-1)
	elif n < 7 and n == 4:
		print(0)
	else:
		while n % 7 != 0:
			n = n - 4
			if n < 0:
				break
		if n < 0:
			print(-1)
		else:
			print(n)


for _ in range(int(input())):
	n = int(input())
	flag = 0
	for x in range(7):
		if n - x * 4 < 0:
			break
		if (n - x * 4) % 7 == 0:
			flag = 1
			print(n - x * 4)
			break
	if flag == 0:
		print(-1)


t = input()
for c in range(0, int(t)):
	n = input()
	temp = int(n)
	while temp > 0:
		if temp % 7 == 0:
			break
		temp = temp - 4
	if temp >= 0:
		print(temp)
	else:
		print(-1)


def calm(ujju):
	waq = 0
	while ujju >= 7:
		if ujju % 7 == 0:
			waq = ujju
			break
		else:
			ujju = ujju - 4
	return waq
ram = int(input())
for jyo in range(ram):
	ujju = int(input())
	if ujju % 7 == 0:
		waq = ujju
	elif calm(ujju - 4):
		waq = calm(ujju - 4)
	elif ujju % 4 == 0:
		waq = 0
	else:
		waq = -1
	print(waq)


try:
	for _ in range(int(input())):
		n = int(input())
		i = n
		while i % 7 != 0:
			i = i - 4
		if (n - i) % 4 == 0 and i >= 0:
			print(i)
		else:
			print(-1)
except EOFError:
	pass


for T in range(int(input())):
	n = int(input())
	for sev in range(7):
		if n - sev * 4 < 0:
			print(-1)
			break
		elif (n - sev * 4) % 7 == 0:
			print(n - sev * 4)
			break


for _ in range(int(input())):
	N = int(input())
	flag = False
	nf = N // 7
	for f in range(nf, -1, -1):
		rem = N - f * 7
		if rem % 4 == 0:
			flag = True
			break
	print(7 * f if flag else -1)


T = int(input())
for i in range(T):
	N = int(input())
	found = False
	while N >= 0:
		if N % 7 == 0:
			found = True
			print(N)
			break
		N = N - 4
	if found == False:
		print(-1)


tests = int(input())
for i in range(tests):
	n = int(input())
	x = n // 7
	rem = n - x * 7
	while x >= 0 and rem % 4 != 0:
		x -= 1
		rem = n - x * 7
	if x >= 0:
		print(x * 7)
	else:
		print(-1)


for _ in range(int(input())):
	n = int(input())
	a = 0
	b = 0
	while n > 0:
		if n % 7 == 0:
			b += n
			n = 0
		else:
			a += 4
			n -= 4
	if n != 0:
		print(-1)
	else:
		print(b)


t = int(input())
for _ in range(t):
	n = int(input())
	a = int(n / 7)
	for i in range(a, -1, -1):
		c = n - 7 * i
		if c % 4 == 0:
			flag = 1
			break
		else:
			flag = 2
	if flag == 1:
		print(n - c)
	elif flag == 2:
		print(-1)


for test in range(int(input())):
	n = int(input())
	var = n // 7 * 7
	while var >= 0:
		if var % 7 == 0 and (n - var) % 4 == 0:
			print(var)
			break
		var -= 7
	else:
		print(-1)


t = int(input())
for ni in range(t):
	n = int(input())
	while n >= 0:
		if n % 7 == 0:
			print(n)
			break
		else:
			n = n - 4
	else:
		print(-1)


for _ in range(int(input())):
	n = int(input())
	if n % 7 == 0:
		print(n)
	else:
		while n % 7 != 0 and n > 0:
			n = n - 4
		if n % 7 == 0:
			print(n)
		else:
			print(-1)


for _ in range(int(input())):
	n = int(input())
	r = n % 7
	if r:
		if r == 1 or r == 5:
			x = n // 7 - 1
		elif r == 2 or r == 6:
			x = n // 7 - 2
		elif r == 3:
			x = n // 7 - 3
		elif r == 4:
			x = n // 7
		if x < 0:
			print(-1)
		else:
			print(7 * x)
	else:
		print(n)


t = int(input())
for i in range(t):
	n = int(input())
	for i in range(7):
		if n - i * 4 < 0:
			print(-1)
			break
		elif (n - i * 4) % 7 == 0:
			print(n - i * 4)
			break


vojj = int(input())
for vishnesh in range(vojj):
	n = int(input())
	if n < 7 and n != 4:
		print(-1)
	elif n < 7 and n == 4:
		print(0)
	else:
		while n % 7 != 0:
			n = n - 4
			if n < 0:
				break
		if n < 0:
			print(-1)
		else:
			print(n)