Số Hamming

Số Hamming là các số nguyên dương chỉ có các ước nguyên tố là \(2, 3, 5\) (nó không chia hết cho số nguyên tố nào ngoài \(2, 3, 5\)).

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

Input

• Dòng đầu tiên gồm số nguyên \(q\) (\(1 \le q \le 10^5\)).

• \(q\) dòng tiếp theo, mỗi dòng gồm một số tự nhiên \(m\) (\(1 \le m \le 10^{18}\)).

Output

In ra \(q\) dòng, dòng thứ \(i\) là kết quả của truy vấn \(i\). Nếu \(m\) không phải số Hamming, in ra \(-1\).

Example

Input:

5
1
2
3
4
7

Output:

1
2
3
4
-1