题目描述

给你一个整数$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$；否则输出操作的最少次数

样例

7
1
10
25
30
14
27
1000000000000000000

0
4
6
6
-1
6
72