C. Optimal Time
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Define the set $$$S(x)$$$ as:

$$$$$$ S(x) = \left\{d \mid d \mid x\right\} \cup \left\{kx \mid 2 \leq k \leq \left\lfloor \frac{N}{x} \right\rfloor \right\} $$$$$$

In simple terms, $$$S(x)$$$ is the union of all divisors of $$$x$$$ and all multiples of $$$x$$$ that do not exceed $$$N$$$.

Assume your current state is $$$x$$$. Every second, you have two choices:

  • Randomly change to a number in $$$S(x)$$$ with equal probability.
  • Do nothing.

At the end of each second, $$$x \leftarrow x-1$$$.

You are required to find the expected time to reach the state $$$0$$$ under optimal decision-making.

Little A wants to know the expected time to reach $$$0$$$ for different values of $$$x$$$ under optimal decision-making, so he has $$$Q$$$ queries. Please help him answer these questions.

Input

The first line contains two positive integers $$$N, Q$$$ $$$(1 \leq N,Q \leq 10^5)$$$, representing the size of the value range and the number of queries.

The next $$$Q$$$ lines each contain a positive integer $$$x$$$ $$$(1 \leq x \leq N)$$$, representing a single query.

Output

For each query, you need to output a real number.

If the absolute or relative error compared to the correct answer does not exceed $$$10^{-6}$$$, it will be considered a correct answer.

Examples
Input
3 2
3
2
Output
1.7500000000
1.5000000000
Input
1000 2
114
514
Output
4.7506538205
3.7750763456