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, ith is the answer for query i. If m is not a Hamming number, print -1.
### Constraints
- 1≤q≤105.
- 1≤m≤1018.
### Example
Input:
512347
Output:
1234-1