You are given several queries. In the i-th query you are given a single positive integer n_{i}. You are to represent n_{i} as a sum of maximum possible number of composite summands and print this maximum number, or print -1, if there are no such splittings.

An integer greater than 1 is composite, if it is not prime, i.e. if it has positive divisors not equal to 1 and the integer itself.


-----Input-----

The first line contains single integer q (1 ≤ q ≤ 10^5) — the number of queries.

q lines follow. The (i + 1)-th line contains single integer n_{i} (1 ≤ n_{i} ≤ 10^9) — the i-th query.


-----Output-----

For each query print the maximum possible number of summands in a valid splitting to composite summands, or -1, if there are no such splittings.


-----Examples-----
Input
1
12

Output
3

Input
2
6
8

Output
1
2

Input
3
1
2
3

Output
-1
-1
-1



-----Note-----

12 = 4 + 4 + 4 = 4 + 8 = 6 + 6 = 12, but the first splitting has the maximum possible number of summands.

8 = 4 + 4, 6 can't be split into several composite summands.

1, 2, 3 are less than any composite number, so they do not have valid splittings.

Difficulty: interview

Starter code:

Solutions:
q = int(input())
for i in range(q):
    n = int(input())
    if n % 4 == 0:
        print(n // 4)
    elif n % 4 == 1 and n // 4 >= 2:
        print(n // 4 - 1)
    elif n % 4 == 2 and n // 4 >= 1:
        print(n // 4)
    elif n % 4 == 3 and n // 4 >= 3:
        print(n // 4 - 1)
    else:
        print(-1)

q = int(input())
ans = []
for i in range(q):
    n = int(input())
    if n % 4 == 0:
        ans.append(n // 4)
    elif n % 4 == 2:
        if n >= 6:
            ans.append(n // 4)
        else:
            ans.append(-1)
    elif n % 4 == 1:
        if n >= 9:
            ans.append(n // 4 - 1)
        else:
            ans.append(-1)    
    else:
        if n >= 15:
            ans.append(n // 4 - 1)
        else:
            ans.append(-1)   
for i in ans:
    print(i)

q = int(input())
for i in range(q):
    n = int(input())
    if n < 4 or n == 7 or n == 5 or n == 11:
        print(-1)
    elif n % 2 == 0:
        print(n // 4)
    else:
        print(n // 4 - 1)

n = int(input())
for i in range(n):
    a = int(input())

    if a % 4 == 0:
        print(a // 4)
    elif (a - 6) >= 0 and (a - 6) % 4 == 0:
        print(((a - 6) // 4) + 1)
    elif (a - 9) >= 0 and (a - 9) % 4 == 0:
        print(((a - 9) // 4) + 1)
    elif (a - 15) >= 0 and (a - 15) % 4 == 0:
        print(((a - 15) // 4) + 2)
    else:
        print(-1)


n = int(input())
arr = []
for i in range(n):
    arr.append(int(input()))
ans = []
for i in range(n):
    q = arr[i]
    if q % 2 == 0 and q >= 4:
        ans.append(q // 4)
    elif q % 2 == 1 and (q >= 13 or q == 9):
        ans.append(1 + ((q - 9) // 4))
    else:
        ans.append(-1)
for i in range(n):
    print(ans[i])


q=int(input())
a=[int(input()) for i in range(0,q)]
def f(w):
    if w in [1,2,3,5,7,11]:
        return -1
    g=0
    if w%2==1:
        w-=9
        g=1
    return w//4+g
for i in a:
    print(f(i))

q = int(input())
for i in range(q):
    a = int(input())
    if a % 2:
        if a == 9:
            print(1)
        elif a - 9 > 2:
            print((a - 9) // 4 + 1)
        else:
            print(-1)
    else:
        if a > 2:
            print(a // 4)
        else:
            print(-1)

#!/usr/bin/env python3

# min odd non-prime is 9
# min even non-prime in 4, NO even numbers gt 2 are primes

def m(n):
    if n == 9:
        return 1
    elif n < 4:
        return -1
    c = 0
    if n % 2:
        if n >= 13:
            c += 1
            n -= 9
        else:
            return -1
    if not ((n - 2) % 4):
        n -= 2
    if not n % 4:
        return c + n // 4

def __starting_point():
    for i in range(int(input())):
        print(m(int(input())))

__starting_point()

q = int(input())
ans = [-1, -1, -1, -1, 1, -1, 1, -1, 2, 1, 2, -1, 3, 2, 3, 2, 4, 3, 4, 3]
for i in range(q):
    n = int(input())
    if n <= 19:
        print(ans[n])
    else:
        if n % 4 == 0:
            print(n // 4)
        if n % 4 == 1:
            print(n // 4 - 1)
        if n % 4 == 2:
            print(n // 4)
        if n % 4 == 3:
            print(n // 4 - 1)

q=int(input())
for i in range(q):
    n=int(input())
    os=n%4
    ce=n//4
    if n==1 or n==2 or n==3 or n==5 or n==7 or n==11:
        print(-1)
    elif os==0 or os==2:
        print(ce)
    elif os==1 or os==3:
        print(ce-1)


from math import floor

q = int(input())
n = [int(input()) for i in range(0, q)]

for k in n:
    x = floor(k/4) - (k % 2)
    if x > 0 and k != 11:
        print(x)
    else:
        print(-1)


easy = [1, 2, 3, 5, 7, 11]

def cheker(i):
    if i in easy:
        print(-1)
    elif i % 2 == 0 and i % 4 != 0:
        if i == 6:
            print(1)
        else:
            print(1 + (i - 6)//4)
    elif i % 4 == 0:
        print(i//4)
    elif (i - 1) % 4 == 0:
        if i == 9:
            print(1)
        else:
            print(1 + (i - 9) // 4)
    elif (i + 1) % 4 == 0:
        print((i-9-6)//4 + 2)




l = int(input())
for i in range(l):
    now = int(input())
    cheker(now)


n = int(input())
for i in range(n):
    a = int(input())
    if a % 4 == 0:
        print(a // 4)
    elif a % 4 == 2:
        a -= 6
        if a < 0:
            print(-1)
        else:
            print(a // 4 + 1)
    elif a % 4 == 1:
        a -= 9
        if a < 0:
            print(-1)
        else:
            print(a // 4 + 1)
    else:
        a -= 15
        if a < 0:
            print(-1)
        else:
            print(a // 4 + 2)

q = int(input())
a = [-1, -1, -1, -1, 1, -1, 1, -1, 2, 1, 2, -1]
for i in range(q):
    n = int(input())
    if n <= 11:
        print(a[n])
    else:
        ans = n // 4
        if n % 2 == 1:
            ans -= 1
        print(ans)


n=int(input())
m=[]
for i in range(n):
    m.append(int(input()))
for i in m:
    if (i%2==0):
        if (i>=4):
            print(i//4)
        else:
            print(-1)
    else:
        if (i==9) or (i>=13):
            print((i-9)//4+1)
        else:
            print(-1)

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

def main():
    n = int(input())
    arr = [-1, -1, -1, -1, 1, -1, 1, -1, 2, 1, 2, -1]
    for i in range(n):
        a = int(input())
        if (a >= 12):
            print(a // 4 - a % 2)
        else:
            print(arr[a])

def __starting_point():
    main()

__starting_point()

n = int(input())
for i in range(n):
    z = int(input())
    if z in range(1,12):
        if z in (8,10):
            ans = 2
        elif z in (1,2,3,5,7,11):
            ans = -1
        else:
            ans = 1
    else:
        ans = (z // 4) - (z % 2)
    print(ans)

q = int(input())
for i in range(q):
    n = int(input())
    if n%2 == 0:
        if n % 4 == 0:
            print(n//4)
        elif n == 2:
            print(-1)
        else:
            print(1 + ((n-6)//4))
    else:
        if n < 9:
            print(-1)
        else:
            t = n - 9
            if t % 4 == 0:
                print(1 + (t//4))
            elif t == 2:
                print(-1)
            else:
                print(2 + ((t - 6)//4))

n = int(input())
for i in range(n):
  a = int(input())
  if a%2 == 0:
    if a < 4:
      print(-1)
    else:
      print(a//4)
  else:
    if a < 9:
      print(-1)
    else:
      if a - 9 < 4 and a - 9 > 0:
        print(-1)
      else:
        print(1 + (a-9)//4)

n=int(input())
a=[0,-1,-1,-1,1,-1,1,-1,2,1,2,-1,3]
b=[3,2,3,2,4,3,4,3,5,4,5,4]
for i in range(n):
    x=int(input())
    if (x<=12):
        print(a[x])
    else:
        print(((x-12)//12)*3+b[x%12])


def shis(k):
    if ((k%2)==0 and k>2):
        return(k//4)
    elif (((k%2)==1 and (k>=13)) or k==9):
        return((k-9)//4+1)
    else:
        return(-1)
m1=[]
n=int(input())
for i in range(n):
  m1.append(int(input()))
for i in range(n):
  print(shis(m1[i]))


n=int(input())
for i in range(n):
    a=int(input())
    if a % 4==0:
        print(a//4)
    elif a%2==1:
        if a<9:
            print(-1)
        elif a==9:
            print(1)
        else:
            a=a-9
            x=a%4
            k=3
            while x < a:
                x+=4
                k=0
                for i in range(2,int(x**0.5+1)):
                    if x % i ==0:
                        k=1
                        break
                if k==1:
                    print((a-x)//4+2)
                    k=2
                    break
            if x > a or k==3 or k==0:
                print(-1)
            elif x==a and k!=2:
                print(2)
    else:
        x=a%4
        k=3
        while x < a:
            x+=4
            k=0
            for i in range(2,int(x**0.5+1)):
                if x % i ==0:
                    k=1
                    break
            if k==1:
                print((a-x)//4+1)
                k=2
                break
        if x > a or k==3 or k==0:
            print(-1)
        elif x==a and k!=2:
            print(1)
    
                    


n = int(input())
ans = ''
for i in range(n):
    a = int(input())
    if a % 2 != 0:
        b = (a - 9) // 4
        if a == 1 or a == 3 or a == 5 or a == 7 or a == 11:
            ans += '-1\n'
        else:
            ans += str(b + 1) + '\n'
    else:
        b = a // 4
        if a < 4:
            ans += '-1\n'
        else:
            ans += str(b) + '\n'
print(ans[:-1])

q=int(input())
for i in range(q):
    a=int(input())
    k=0
    if a==11:
        print(-1)
        continue
    if a%2==1:
        if a<9:
            print(-1)
            continue
        else:
            a-=9
            k+=1
    k+=a//4
    a%=4
    if k>0:
        print(k)
    else:
        print(-1)

import sys
n=int(input())
pr=[1,2,3,5,7,11]
for i in range(n):
    k=int(input())
    if k in pr:
        print(-1)
        continue
    if k%2==0:print(k//4)
    else:print((k-9)//4+1)