Processing math: 100%
Hamming number - MarisaOJ: Marisa Online Judge

Hamming number

Time limit: 1000 ms
Memory limit: 256 MB
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