Hamming number - MarisaOJ: Marisa Online Judge

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$

Topic

Complete Search

Binary search

Rating

1200

Solution (2)

Solution