Hamming numbers are positive integers having only $2, 3, 5$ as their prime factors (i.e. they divisible by no prime other than $2, 3, 5$).
You are given $q$ queries, each is an integer $m$. Write down all Hamming number in ascending order, find the position of $m$ in the list (the list index starts at $1$).
### Input
- The first line contains an integers $q$.
- The next $q$ lines, each line contains an integer $m$.
### Output
- Print $q$ lines, $i^{th}$ is the answer for query $i$. If $m$ is not a Hamming number, print `-1`.
### Constraints
- $1 \le q \le 10^5$.
- $1 \le m \le 10^{18}$.
### Example
Input:
```
5
1
2
3
4
7
```
Output:
```
1
2
3
4
-1
```
