题目描述

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

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

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

输入格式

第一行，一个正整数 $n$，表示有 $n$ 个问题。

接下来 $n$ 行，每行一个正整数 $x$。

输出格式

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

样例 #1

7
1
2
3
12
12345
15116544
387420489

0
-1
2
-1
-1
12
36

样例解释

• $x = 1$：已经是 $1$，需要 $0$ 步。
• $x = 2$：只能乘 $2$ 变成 $4,8,16,\ldots$，永远无法变成 $1$，输出 $-1$。
• $x = 3$：$3 \times 2 = 6$，$6 / 6 = 1$，需要 $2$ 步。
• $x = 12$：$12 / 6 = 2$，此后无法变成 $1$，输出 $-1$。

数据范围

$1 \le n \le 1000$，$x \le 10^9$。