Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
B. Multiply by 2, divide by 6

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou are given an integer $$$n$$$. In one move, you can either multiply $$$n$$$ by two or divide $$$n$$$ by $$$6$$$ (if it is divisible by $$$6$$$ without the remainder).

Your task is to find the minimum number of moves needed to obtain $$$1$$$ from $$$n$$$ or determine if it's impossible to do that.

You have to answer $$$t$$$ independent test cases.

Input

The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — the number of test cases. Then $$$t$$$ test cases follow.

The only line of the test case contains one integer $$$n$$$ ($$$1 \le n \le 10^9$$$).

Output

For each test case, print the answer — the minimum number of moves needed to obtain $$$1$$$ from $$$n$$$ if it's possible to do that or -1 if it's impossible to obtain $$$1$$$ from $$$n$$$.

Example

Input

7 1 2 3 12 12345 15116544 387420489

Output

0 -1 2 -1 -1 12 36

Note

Consider the sixth test case of the example. The answer can be obtained by the following sequence of moves from the given integer $$$15116544$$$:

- Divide by $$$6$$$ and get $$$2519424$$$;
- divide by $$$6$$$ and get $$$419904$$$;
- divide by $$$6$$$ and get $$$69984$$$;
- divide by $$$6$$$ and get $$$11664$$$;
- multiply by $$$2$$$ and get $$$23328$$$;
- divide by $$$6$$$ and get $$$3888$$$;
- divide by $$$6$$$ and get $$$648$$$;
- divide by $$$6$$$ and get $$$108$$$;
- multiply by $$$2$$$ and get $$$216$$$;
- divide by $$$6$$$ and get $$$36$$$;
- divide by $$$6$$$ and get $$$6$$$;
- divide by $$$6$$$ and get $$$1$$$.

Codeforces (c) Copyright 2010-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/28/2022 00:37:28 (g2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|