Một số được gọi là Composite khi:

• Nó không phải là số nguyên tố,
• Nó là số nguyên dương lớn hơn 1.

Cho số nguyên dương ~N~, hãy tính số lượng số Composite nhiều nhất có thể để tạo thành số ~N~.

Input

Dòng đầu tiên ghi số nguyên ~T~ là số bộ test ~(1 \le T \le 1000)~,

~T~ dòng tiếp theo ghi số nguyên dương ~N (1 \le N \le 10^{18})~.

Output

Với mỗi bộ test, ghi ~1~ số nguyên dương là kết quả của bài toán nếu không tìm được số thõa mãn thì in ra ~-1~.

Sample

Input #1

2
8
5

Output #1

2
-1

Hint

Ở #1:

• số ~8~ có thể phân tích thành ~4 + 4~,
• số ~5~ không thể phân tích thành tổng các số Composite.