小 C 有一个整数 n，小 K 给了小 C 三种变换：

• 如果 2|n，则可以让 n\leftarrow \frac{n}{2}。

• 如果 3|n，则可以让 n\leftarrow \frac{2n}{3}。

• 如果 5|n，则可以让 n\leftarrow \frac{4n}{5}。

小 C 现在想要把 n 变为 1，他想知道将 n 变为 1 的最少次数，如果不可能将 n 变为 1，请告诉小 C 不可能（输出 -1）。

由于小 C 是好奇宝宝，他有 T 组询问需要你来解答。

输入的第一行，包含一个正整数 T，表示询问个数。

接下来 T 行，每行一个正整数 n，表示小 C 询问的 n。

输出共 T 行，包含一个整数，即变换的最少次数，若不可能则输出 -1。

数据规模与约定

• 对于 30\% 的数据，保证 n \le 100。

• 对于另 30\% 的数据，保证 n \le 10^5。

• 对于 100\% 的数据，保证 1 \le n \le 10^{18}，1\le T\le 10^3。