#P1176A. Divide it!

    ID: 706 远端评测题 1000ms 256MiB 尝试: 3 已通过: 0 难度: 10 上传者: 标签>brute forcegreedyimplementation*800已翻译

Divide it!

描述

给你一个整数 n。

你可以对这个数进行任意次数(可能为零)的以下操作之一:

  1. 如果 n 能被 2 整除,则将 n 替换为 n/2;
  2. 如果 n 能被 3 整除,则将 n 替换为 2n/3;
  3. 如果 n 能被 5 整除,则将 n 替换为 4n/5。

例如,你可以使用第一种操作将 30 替换为 15,使用第二种操作将 30 替换为 20,或者使用第三种操作将 30 替换为 24。

你的任务是找到从 n 得到 1 所需的最小移动次数,或者判断无法实现。

你需要回答 q 个独立的查询。

输入

输入的第一行包含一个整数 q(1 ≤ q ≤ 1000)——查询的数量。

接下来 q 行包含查询。对于每个查询,你会给出一个整数 n(1 ≤ n ≤ 10^18)。

输出

对于每个查询,打印答案在一行中。如果无法从 n 得到 1,则打印 -1。否则,请打印所需的最小移动次数。

示例

7
1
10
25
30
14
27
1000000000000000000
0
4
6
6
-1
6
72

Description

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.

Input

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}$).

Output

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.

Samples

7
1
10
25
30
14
27
1000000000000000000
0
4
6
6
-1
6
72