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.

-----Example-----
Input:
5
7
4
11
1
15

Output:
7
0
7
-1
7

Explanation
For the last test case, N = 15, the smallest lucky lucky number is
444444477777777. The count of digit 4 is 7.

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
import sys
import os

def __starting_point():
	start = 0
	for line in sys.stdin:
		if start == 0:
			start = 1
			continue
		else:
			try:
				n = int(line.strip())
				q = n / 7
				rem = n % 7
				if rem == 0:
					res = n
				elif rem == 1:
					res = (q - 1) * 7
				elif rem == 2:
					res = (q - 2) * 7
				elif rem == 3:
					res = (q - 3) * 7
				elif rem == 4:
					res = q * 7
				elif rem == 5:
					res = (q - 1) * 7
				elif rem == 6:
					res = (q - 2) * 7
				if res < 0:
					print(-1)
				else:
					print(res)
			except:
				break
__starting_point()


from sys import stdin

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

def getInts():
	return [int(z) for z in stdin.readline().split()]
for case in range(getInt()):
	N = getInt()
	while N >= 0 and N % 7 != 0:
		N -= 4
	if N < 0:
		N = -1
	print(N)


import itertools
import sys
inp = sys.stdin
out = sys.stdout
cases = int(inp.readline())

def lucky_number_4(num):
	if num < 4:
		return -1
	if num == 4:
		return 0
	if num < 7:
		return -1
	fours = num - num % 7
	for i in range(fours, 0, -7):
		if (num - i) % 4 == 0:
			return i
	return -1
outputs = []
for case in range(1, cases + 1):
	num = int(inp.readline())
	fours = lucky_number_4(num)
	out.write(str(fours) + '\n')


def solve(D):
	c4 = D
	while c4 >= 0:
		if c4 % 7 == 0:
			c7 = D - c4
			if c7 % 4 == 0:
				return c4
		c4 -= 4
	return -1
for _t in range(int(input())):
	print(solve(int(input())))


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


def calc_x(y, num):
	return (num - 4 * y) / 7.0
num_test_cases = int(input())
for i in range(num_test_cases):
	num = int(input())
	current_y = 0
	result_x = 0
	while result_x >= 0:
		result_x = calc_x(current_y, num)
		if result_x % 1 == 0:
			break
		current_y += 1
	if result_x < 0 and current_y > 0:
		print(-1)
	else:
		print(int(result_x * 7))


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


import sys

def readInput(stream):
	T = int(sys.stdin.readline())
	Ns = []
	for Tit in range(T):
		Ns.append(int(sys.stdin.readline()))
	return Ns

def isInt(myInt):
	return myInt - int(myInt) == 0.0

def getMaxFour(N):
	b = 1000.0
	a = -1.0
	while b > 0.0:
		a = a + 1.0
		b = (N - 4.0 * a) / 7.0
		if isInt(b):
			return int(b * 7)
	return -1

def __starting_point():
	Ns = readInput(sys.stdin)
	for N in Ns:
		slevin = getMaxFour(N)
		print(slevin)
__starting_point()


try:
	import psyco
	psyco.full()
except ImportError:
	pass

def main(n):
	sol = -1
	while n >= 7 and sol < 0:
		if not n % 7:
			sol = n
		n -= 4
	return sol

def __starting_point():
	T = int(input())
	for test in range(T):
		N = list(map(int, input().split()))[0]
		print(main(N))
__starting_point()


import sys, time, math
testCases = int(sys.stdin.readline())
for i in range(testCases):
	fours = 0
	N = int(sys.stdin.readline())
	fours = N / 7 * 7
	n = int(N)
	while fours >= 0:
		if (n - fours) % 4 == 0:
			break
		else:
			fours -= 7
	if fours >= 0:
		sys.stdout.write('%d\n' % fours)
	else:
		sys.stdout.write('-1\n')


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


for _ in range(int(input())):
	n = int(input())
	if n % 7 == 0:
		print(n)
	elif n < 17 and n == 1 or n == 2 or n == 3 or (n == 5) or (n == 6) or (n == 9) or (n == 10) or (n == 13) or (n == 17):
		print(-1)
	else:
		found = False
		while not found:
			n -= 4
			if n % 7 == 0:
				print(n)
				found = True
			elif n % 4 == 0:
				temp = n
				while temp > 0:
					temp -= 4
					if temp % 7 == 0:
						break
				if temp > 0 and temp % 7 == 0:
					print(temp)
				else:
					print(0)
				found = True


i = 0
test_num = eval(input())
while i < test_num:
	r = 0
	index = 0
	new_inp = 0
	inp = input()
	inp_list = list(inp)
	for digit in reversed(inp_list):
		d = int(digit)
		if index % 6 == 0:
			r = r + d * 1
		if index % 6 == 1:
			r = r + d * 3
		if index % 6 == 2:
			r = r + d * 2
		if index % 6 == 3:
			r = r + d * 6
		if index % 6 == 4:
			r = r + d * 4
		if index % 6 == 5:
			r = r + d * 5
		index += 1
		r = r % 7
	if r == 0:
		print(inp)
	elif r % 4 == 0:
		print(int(inp) - r)
	else:
		new_inp = int(inp) - r
		j = 1
		while True:
			if new_inp == 0:
				print('-1')
				break
			elif r + j * 7 < int(inp):
				if (r + j * 7) % 4 == 0:
					print(new_inp - j * 7)
					break
			else:
				print('-1')
				break
			j += 1
	i += 1


def main():
	for i in range(int(input())):
		n = int(input())
		numberFound = False
		sevens = 0
		while sevens <= n:
			if (n - sevens) % 7 == 0:
				numberFound = True
				print(n - sevens)
				break
			sevens += 4
		if not numberFound:
			print(-1)

def __starting_point():
	main()
__starting_point()