Problem Setter: M M Mehedi Hasan

Intake 33, Department of CSE

Mr. MMMH is a shopkeeper. He sells n types of chocolates, from 1 to n (1 <= n <= 10⁷). She has K amount of money. She wants to buy the maximum number of types of chocolates.

The cost of chocolates are,

The cost of type 1 = The summation of divisors of 1 = 1.

The cost of type 2 = The summation of divisors of 2 = 1 + 2 = 3.

The cost of type 3 = The summation of divisors of 3 = 1 + 3 = 4.

And so on….

Check the Input/Output section for further information.

Input Format

You are given two integers n (1 <= n <= 10⁷) and q (1 <= q <= 10⁵). Here, n is the number of types of chocolates, and q is the number of test cases.

In each case, you are given one integer k (1 <= k <= 10¹⁶), which is the amount of the money of Suborno.

Output Format

You should find out, the maximum number of types of chocolates she can buy using k amount of money from 1 to n types of chocolates under the above-illustrated cost conditions.

Samples