题目描述

有一个正整数 $x$，你要把 $x$ 变成 1，每一步你都可以选择如下两种操作的其中一种：

1. 操作1：变大两倍，即 $x = x \times 2$；
2. 操作2：缩小六倍，即 $x = x / 6$，这个操作的前提是 $x$ 除以 6 没有余数。

现在有 $n$ 个问题，每个问题给出一个正整数 $x$，问至少需要多少步，才能使得 $x$ 变成 1；如果永远不可能把 $x$ 变成 1，输出 -1。

输入格式

1. 第一行，一个正整数 $n$，表示有 $n$ 个问题。$1 \leq n \leq 1000$；
2. 第二行，共 $n$ 个正整数，每个正整数代表一个问题的 $x$，其中 $x$ 不超过 $10^9$。

输出格式

输出共 $n$ 行，每行一个整数，代表回答一个问题的答案。

输入输出样例 #1

样例输入 1

7
1
2
3
12
12345
15116544
387420489

样例输出 1

0
-1
2
-1
-1
12
36