Ở đất nước Clue, một cửa hàng bán vải chỉ có bốn loại mảnh vải: loại 1 dài ~1~ mét, loại 2 dài ~3~ mét, loại 3 dài ~6~ mét, loại 4 dài ~7~ mét. Tất cả các mảnh vải đều có chiều rộng 1 mét.

Bạn cần mua chính xác ~n~ mét vải tại cửa hàng này. Hãy tìm số mảnh vải tối thiểu bạn cần mua.

Input

Dòng đầu tiên chứa số nguyên dương ~t~ (~1 \le t \le 10^4~) là số lượng tests.

Mỗi test gồm một số nguyên dương ~n~ duy nhất (~1 \le n \le 363636^3~) thể hiện số mét vải bạn cần mua.

Output

~t~ dòng, mỗi dòng là số mảnh vải tối thiểu bạn cần mua.

Nếu không tồn tại cách mua thỏa mãn, in ra ~-1~.

Sample Input

2
10
14

Sample Output

2
2