Cho một số nguyên dương ~n~. Bạn có thể thực hiện bất kỳ thao tác nào sau đây với số lần tùy ý (có thể là không lần nào):

1. Thay ~n~ bằng ~n/2~ nếu ~n~ chia hết cho 2
2. Thay ~n~ bằng ~2*n/3~ nếu ~n~ chia hết cho 3
3. Thay ~n~ bằng ~4*n/5~ nếu ~n~ chia hết cho 5

Ví dụ: bạn có thể thay ~n = 30~ bằng 15 với thao tác 1, hoặc bằng 20 với thao tác 2 hoặc bằng 24 với thao tác 3.

Nhiệm vụ của bạn là tìm ra số thao tác tối thiểu cần thiết để từ ~n~ ta thu được số 1 hoặc nói rằng không thể thực hiện được.

Bạn phải trả ~q~ truy vấn độc lập.

Dữ liệu vào

• Dòng đầu tiên của đầu vào chứa một số nguyên ~q (1 \leq q \leq 1000)~ là số lượng truy vấn.
• Dòng thứ ~i~ trong ~q~ dòng tiếp theo chứa truy vấn thứ ~i~ gồm một số nguyên ~n (1 \leq n \leq 10^{18})~.

Kết quả

• Chương trình của bạn cần in ra ~q~ dòng, dòng thứ ~i~ chứa câu trả lời cho truy vấn thứ ~i~. Nếu thực hiện được, thì in ra số -1. Nếu có thể thì in ra số lượng thao tác tối thiểu cần thiết để làm điều đó.

Ví dụ 1:

INPUT

7
1
10
25
30
14
27
1000000000000000000

OUTPUT

0
4
6
6
-1
6
72