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.

×
A. Divide it!

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou are given an integer $$$n$$$.

You can perform any of the following operations with this number an arbitrary (possibly, zero) number of times:

- Replace $$$n$$$ with $$$\frac{n}{2}$$$ if $$$n$$$ is divisible by $$$2$$$;
- Replace $$$n$$$ with $$$\frac{2n}{3}$$$ if $$$n$$$ is divisible by $$$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.

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.

Example

Input

7 1 10 25 30 14 27 1000000000000000000

Output

0 4 6 6 -1 6 72

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/02/2021 06:55:23 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|