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