Một miếng kính tráng men có kích thước $n$ rơi từ trên không trung xuống và vỡ thành các mảnh tinh thể, mỗi mảnh tinh thể đều có kích thước là một số nguyên dương.

Aya nhẹ nhàng cầm những mảnh tinh thể lấp lánh này lên. Trong mắt cô, một mảnh tinh thể có kích thước $x$ được gọi là mảnh tinh thể đẹp khi và chỉ khi $x$ là một số lẻ lớn hơn 1.

Với giả thiết rằng tất cả các mảnh tinh thể đều là mảnh tinh thể đẹp, Aya muốn biết giá trị lớn nhất của số lượng mảnh tinh thể. Nếu không tồn tại trường hợp tất cả các mảnh tinh thể đều là mảnh tinh thể đẹp, hãy trả về -1.

Dữ liệu vào

Bài toán gồm nhiều bộ dữ liệu. Dòng đầu tiên chứa một số nguyên dương $T$ ($1 \le T \le 10^4$), biểu thị số lượng bộ dữ liệu.

Đối với mỗi bộ dữ liệu: Một dòng chứa một số nguyên dương $n$ ($1 \le n \le 10^9$), biểu thị kích thước của miếng kính tráng men, tức là tổng kích thước của tất cả các mảnh tinh thể.

Dữ liệu ra

Đối với mỗi bộ dữ liệu: Một dòng chứa một số nguyên, biểu thị số lượng mảnh tinh thể lớn nhất trong trường hợp tất cả các mảnh tinh thể đều là mảnh tinh thể đẹp. Nếu không tồn tại trường hợp tất cả các mảnh tinh thể đều là mảnh tinh thể đẹp, hãy in ra -1.

Ví dụ

Dữ liệu vào 1

6
1
3
5
7
8
9

Dữ liệu ra 1

-1
1
1
1
2
3

Ghi chú

Khi $n = 3, n = 5, n = 7$, số lượng mảnh tinh thể lớn nhất hiển nhiên là 1. Khi $n = 8$, số lượng mảnh tinh thể lớn nhất là 2, khi đó kích thước các mảnh tinh thể lần lượt là 3, 5. Khi $n = 9$, số lượng mảnh tinh thể lớn nhất là 3, khi đó kích thước các mảnh tinh thể lần lượt là 3, 3, 3.