Divide it!

题意翻译

### 题目描述 给你一个整数$n$ 你可以对这个数进行任意多次（可以为$0$）如下的操作 1. 如果$n$是$2$的倍数，把$n$替换成$\frac{n}{2}$ 2. 如果$n$是$3$的倍数，把$n$替换成$\frac{2n}{3}$ 3. 如果$n$是$5$的倍数，把$n$替换成$\frac{4n}{5}$ 举个例子，你可以通过操作$1$把$30$变成$15$，用操作$2$把$30$变成$20$，用操作$3$把$30$变成$24$ 你的任务是找到把$n$变成$1$的最少操作次数，或者说不可能做到 你需要回答$q$个独立的询问 ### 输入输出格式 #### 输入格式 输入的第一行包括一个整数$q$（$1\leq q\leq 1000$）——询问的数量 接下来$q$行每行一个询问，每个询问给你一个$n$（$1\leq n\leq 10^{18}$） #### 输出格式 对于每个询问一行输出一个答案，如果不可能从$n$变成$1$，输出$-1$；否则输出操作的最少次数

题目描述

You are given an integer $ n $ . You can perform any of the following operations with this number an arbitrary (possibly, zero) number of times: 1. Replace $ n $ with $ \frac{n}{2} $ if $ n $ is divisible by $ 2 $ ; 2. Replace $ n $ with $ \frac{2n}{3} $ if $ n $ is divisible by $ 3 $ ; 3. Replace $ n $ with $ \frac{4n}{5} $ if $ n $ is divisible by $ 5 $ . For example, you can replace $ 30 $ with $ 15 $ using the first operation, with $ 20 $ using the second operation or with $ 24 $ using the third operation. Your task is to find the minimum number of moves required to obtain $ 1 $ from $ n $ or say that it is impossible to do it. You have to answer $ q $ independent queries.

输入输出格式

输入格式

The first line of the input contains one integer $ q $ ( $ 1 \le q \le 1000 $ ) — the number of queries. The next $ q $ lines contain the queries. For each query you are given the integer number $ n $ ( $ 1 \le n \le 10^{18} $ ).

输出格式

Print the answer for each query on a new line. If it is impossible to obtain $ 1 $ from $ n $ , print -1. Otherwise, print the minimum number of moves required to do it.

输入输出样例

输入样例 #1

7
1
10
25
30
14
27
1000000000000000000

输出样例 #1

0
4
6
6
-1
6
72