Basically the title. The problem statement can be found here. No idea how to solve it efficiently.

UPDATE 1: why the downvotes?

UPDATE 2: based on the answers so far, the solution would be to exhaustively explore all combinations of exponents k₁, k₂, ..., k_r (k_i ≥ k_j for all i < j) such that and k = 2^k₁ * 3^k₂ * 5^k₃ * 7^k₄ * 11^k₅ * ... < 2⁶³. During the exhaustive search one can map each n to its minimum k found (for instance, using an unordered_map) and then the queries can be answered in O(1). The problem is: how can you estimate the complexity of the exhaustive search? Any easy way to estimate an upperbound for it?

UPDATE 3: pshishod2645 says there are around 2 * 10⁶ valid combinations of exponents, where did he get that number from?