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: interview

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())
                   
               # print n   
                   
                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):#15	
	if num < 4:			#no
		return -1
	if num == 4:		#no
		return 0
	if num < 7:			#no
		return -1
	fours = num - (num % 7) #= 15 - 1 = 14
	for i in range(fours,0,-7): #14, 
		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())))



# code chef may2012  chefluck.py


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


#from datetime import datetime
#import random

def calc_x(y, num):
    return (num - 4 * y) / 7.0

#num_test_cases = 1000

num_test_cases = int(input())

#print datetime.now()

for i in range(num_test_cases):
    #num = random.randint(1, 10)
    num = int(input())
    #print "testing num: %s" % num
    current_y = 0
    result_x = 0
    while result_x >= 0:
        result_x = calc_x(current_y, num)
        #print "result_x: %s when y: %s" % (result_x, current_y)
        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))

#print datetime.now()

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)

'''
Created on 6 mai 2012

@author: Quentin
'''
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.

def getMaxFour(N):
    b = 1000.
    a = -1.
    
    while( b>0. ) :
        a = a + 1.
        b = (N - 4.*a) / 7.
        
        if isInt(b) :
            return int(b * 7)

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

#!/usr/bin/env python2
#-*- coding: utf-8 -*-

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()

# LuckyNumbers.py
# Code Chef Problem: Lucky Lucky Number
#   http://www.codechef.com/MAY12/problems/CHEFLUCK
#   May Long Challenge 2012
# Benjamin Johnson
# May 5 2012 9:35
# Lessons Learned: Math review: 0 is divisible by all numbers

import sys,time,math

#Use the test file when testing
#testInputFile = open("test.in","r")

#Get input here
testCases = int(sys.stdin.readline())
#testCases = int(testInputFile.readline())

for i in range(testCases):
    fours = 0
    #N = int(testInputFile.readline())
    N = int(sys.stdin.readline())
    fours = (N/7)*7 #Will not be N
    n = int(N)
    while fours >= 0:
        # Check to see if N-fours is divisible by 4
        if (n-fours)%4 == 0:
            break;
        else:
            fours -= 7
    if fours >= 0:
        sys.stdout.write("%d\n"%fours)
    else:
        sys.stdout.write("-1\n")
#testInputFile.close()


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
        

#!/usr/bin/python
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)
#print d,index, index%6
		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:			#if the input itself is divisible by 7
		print(inp)
	else:
		if r%4 == 0:		#if the input is not divisible by 7 but remainder is divisible by 4
			print(int(inp) - r)
		else:			#if remainder is not divisible by 4
			new_inp = int(inp) - r
			j = 1
			while True:
				if new_inp == 0:	#for 1,2,3,5,6
					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()

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

def __starting_point():
    main()
__starting_point()

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