Để chào mừng Xuân 2026, Trường THCS X tổ chức một buổi ngoại khoá chủ đề "Ngày xuân Hạnh phúc". Trong buổi ngoại khoá, học sinh sẽ được tham gia các hoạt động: viết câu đối, gói bánh chưng, bày mâm ngũ quả và chơi các trò chơi. Trò chơi Đua thuyền trên cạn được rất nhiều học sinh hưởng ứng.

Theo thể lệ, học sinh các lớp sẽ tham gia chơi với ~2~ nội dung:

• Nội dung 1: mỗi đội có ~5~ học sinh.

• Nội dung 2: mỗi đội có ~3~ học sinh.

Trường có ~T~ lớp. Mỗi lớp có ~n~ học sinh tham gia chơi.

Yêu cầu: Với từng lớp, hãy xác định số đội chơi ít nhất cần lập để đảm bảo có đúng ~n~ học sinh được tham gia.

Input

• Dòng 1: số nguyên dương ~T~ là số lượng lớp ~(1 \le T \le 10^5)~;

• ~T~ dòng tiếp theo, mỗi dòng chứa một số nguyên ~n~ ~(1 \le n \le 5000)~.

Output

Gồm ~T~ dòng, dòng thứ ~i~ in ra số đội chơi ít nhất cần lập để đảm bảo đúng ~n~ học sinh tham gia; In ra ~-1~ nếu không thể lập đội chơi đúng yêu cầu.

Sample Input 1

4
1
8
11
14

Sample Output 1

-1
2
3
4

Notes

• ~1~ học sinh: Không thể lập đội chơi.

• ~8~ học sinh: ~5+3 \rightarrow~ lập được ~2~ đội chơi.

• ~11~ học sinh: ~5+3+3 \rightarrow~ lập được ~3~ đội chơi.

• ~14~ học sinh: ~5+3+3+3 \rightarrow~ lập được ~4~ đội chơi.