20778번 - Combine The Gears 스페셜 저지다국어

With the rapid development of society, the demand for high-precision clocks is constantly rising. Recently, the China Clock Production Company is developing a new type of clock, which can represent a wide range of times.

The novel clock displays the current time in an unusual fashion. The clock consists of several pointers, each controlled by a gear. All gears rotate synchronously -- one tooth per period. However, the numbers of teeth of the gears may differ. If a gear has $t$ teeth, then the corresponding pointer can point to $t$ different directions, denoted $0, 1, 2, \cdots, t-1$, respectively, where $0$ is the initial direction. Furthermore, if a clock is equipped with $n$ pointers, the $i$-th of which is controlled by a $t_i$-tooth gear, then the $i$-th pointer will point to $k \bmod t_i$ after $k$ periods of time.

The price for a $t$-tooth gear is $t$ yuan. Given a total budget of $b$ yuan, you need to design a combination of gears, such that the number of valid combinations of directions of pointers is maximized, and the total cost on gears does not exceed the budget. A combination of directions $(d_1, d_2, \cdots, d_n)$ is valid, if it can be written $$ (k \bmod t_1, k \bmod t_2, \cdots, k \bmod t_n) $$ for some nonnegative integer $k$, where $t_i$ is the number of teeth of the $i$-th gear. Since the answer may be too large, output the answer in natural logarithm (logarithm with base $e = 2.718281828\cdots)$.

The first line of input is a single integer $T$ $(1 \leq T \leq 30\;000)$, indicating the number of test cases. Each test case is a single line of an integer $b$ $(1 \leq b \leq 30\;000)$, denoting the total budget.

For each test case, print the natural logarithm, within an absolute or relative error of no more than $10^{-6}$, of the maximum number of valid combinations, in a single line.

For the second sample data, a 3-tooth gear along with a 4-tooth gear may yield 12 different combinations of directions, with total cost exactly being 7. So you should print the value of $\ln 12$, which is approximately 2.484906650.