Problem: 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.

Solution (in PYTHON):

Solution:
#!/usr/bin/python
"""
http://www.codechef.com/problems/CHEFLUCK

Testing:
    nosetests --with-doctest <file>

Input:
5
7
4
11
1
15

Output:
7
0
7
-1
7
"""


def alg(n):
    """
    >>> alg(7)
    7
    >>> alg(4)
    0
    >>> alg(11)
    7
    >>> alg(1)
    -1
    >>> alg(15)
    7
    """

    # my initial solution
    #while n % 7:
    #    n -= 4
    #if n < 0:
    #    return -1
    #return n
    
    # best solution
    d, m = divmod(n, 7)
    d -= m % 4
    return d * 7 if d >= 0 else -1


if __name__ == "__main__":

    for _ in range(input()):
        print alg(input())