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.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = '#!/usr/bin/python\ni = 0;\ntest_num = eval(input())\nwhile i < test_num:\n\tr = 0;\n\tindex = 0;\n\tnew_inp = 0\n\tinp = input()\n\tinp_list = list(inp);\n\tfor digit in reversed(inp_list):\n\t\td = int(digit)\n#print d,index, index%6\n\t\tif index%6 == 0:\n\t\t\tr = r + d*1\n\t\tif index%6 == 1:\n\t\t\tr = r + d*3\n\t\tif index%6 == 2:\n\t\t\tr = r + d*2\n\t\tif index%6 == 3:\n\t\t\tr = r + d*6\n\t\tif index%6 == 4:\n\t\t\tr = r + d*4\n\t\tif index%6 == 5:\n\t\t\tr = r + d*5\n\t\tindex += 1;\n\t\tr = r%7\n\tif r == 0:\t\t\t#if the input itself is divisible by 7\n\t\tprint(inp)\n\telse:\n\t\tif r%4 == 0:\t\t#if the input is not divisible by 7 but remainder is divisible by 4\n\t\t\tprint(int(inp) - r)\n\t\telse:\t\t\t#if remainder is not divisible by 4\n\t\t\tnew_inp = int(inp) - r\n\t\t\tj = 1\n\t\t\twhile True:\n\t\t\t\tif new_inp == 0:\t#for 1,2,3,5,6\n\t\t\t\t\tprint("-1")\n\t\t\t\t\tbreak;\n\t\t\t\telif r + j*7 < int(inp):\n\t\t\t\t\tif (r + j*7)%4 == 0:\n\t\t\t\t\t\tprint(new_inp - j*7)\n\t\t\t\t\t\tbreak\n\t\t\t\telse: \n\t\t\t\t \tprint("-1")\n\t\t\t\t \tbreak;\n\t\t\t\tj+=1\n\ti+=1\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 17085