Số Hamming là các số nguyên dương chỉ có ~2~, ~3~, ~5~ là ước nguyên tố (nghĩa là chúng không chia hết cho bất kỳ số nguyên tố nào khác ngoài ~2~, ~3~, ~5~).

Cho ~q~ truy vấn, mỗi truy vấn là một số nguyên ~m~. Viết ra tất cả các số Hamming theo thứ tự tăng dần, hãy tìm vị trí của ~m~ trong danh sách đó (danh sách được đánh chỉ số bắt đầu từ ~1~).

Dữ liệu vào

• Dòng đầu tiên chứa một số nguyên ~q~.
• ~q~ dòng tiếp theo, mỗi dòng chứa một số nguyên ~m~.

Kết quả

In ra ~q~ dòng, dòng thứ ~i~ là đáp án cho truy vấn thứ ~i~. Nếu ~m~ không phải số Hamming, in ra ~-1~.

Ví dụ

Đầu vào:

5
1
2
3
4
7

Đầu ra:

1
2
3
4
-1

Giải thích: Các số Hamming đầu tiên là ~1, 2, 3, 4, 5, 6, 8, 9, 10, 12, \ldots~ Số ~7~ có ước nguyên tố ~7~ nên không phải số Hamming.

Giới hạn

• ~1 \le q \le 10^5~
• ~1 \le m \le 10^{18}~

Lưu ý rằng ~1 = 2^0 \cdot 3^0 \cdot 5^0~ cũng là một số Hamming. Có ~10917~ số Hamming không vượt quá ~10^{18}~.