You are given several queries. In the i-th query you are given a single positive integer ni. You are to represent ni 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 ≤ 105) — the number of queries.

q lines follow. The (i + 1)-th line contains single integer ni (1 ≤ ni ≤ 109) — 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.
import java.io.IOException;
import java.util.*;
 
public class we {
	//public static int[] dp = new int[1000000000];
	public static boolean check(int x) {
		if(x==0)return true;
		for(int i=2;i<=Math.sqrt(x);i++) {
			if(x%i==0)
				return true;
		}
		return false;
	}
//	public static int f(int x) {
//		//System.out.println(x);
//		if(x==0)
//			return 0;
//		if(x<4)
//			return -1000000;
//		if(dp[x]!=0) {
//			return dp[x];
//		}else {
//			int max = -100000;
//			for(int i=4;i<=x;i++) {
//				if(check(i)) {
//					int a = 1+f(x-i);
//					if(max<a)
//						max = a;
//				}
//			}
//			return (dp[x]=max);
//			}
//	}
	
	public static int F(int q) {
		int r = 0;
		if(q%4==0)
			return q/4;
		else if(q%4==1 &&q/4>1)
			return q/4-1;
		else if(q%4==2 && q/4>0)
			return q/4;
		else if(q%4==3 && q/4>2)
			return q/4 -1;
		return -1;
	}
	//System.out.println(Arrays.toString(dp));
	//System.out.println(check(5));
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		for(int i=0;i<n;i++) {
			int q = sc.nextInt();
			int a = F(q);
			System.out.println(a);
		}
		
	}
}