题目描述

佩奇和乔治玩游♂戏。

佩奇在黑板上写下数字 $\{1,2,\cdots,n\}$ ，每次他们会等概率地报出黑板上的一个数字 $x$ ,并删除所有 $x$ 的正整数次幂。

形式化地,给定数列 $\{1,2,\cdots,n\}$ ，每次等概率选出数列中存在的 $1$ 个数字 $x$ ，并将形如 $\{x^k,k \in Z^{+}\}$ 的数字删除。

他们玩了整整一个下午，游戏还是没有结束，所以他们想知道，该游戏期望在多少轮后会结束。

如果你的答案与正确答案的绝对误差在 $10^{-4}$以内，则被判定为正确。

输入格式

第一行 $1$ 个正整数 $t$,表示佩奇和乔治打算玩 $t$ 轮游戏。

之后 $t$ 行,每行 $1$ 个正整数 $n$,表示佩奇在黑板上写下了数字 $\{1,2,\cdots,n\}$ 并将进行游戏。

输出格式

一共 $t$ 行，每行 $1$ 个小数,表示答案，答案保留小数。

如果你的答案与正确答案的绝对误差在 $10^{-4}$以内，则被判定为正确。

5
4
8
16
32
100

3.50000000
7.00000000
13.83333333
28.33333333
93.41666667

提示

对于 $n=4$，

若删除的顺序为 $\{1,2,3\},\{3,2,1\}$, 那么概率为$\frac{1}{4} \times \frac{1}{3} \times \frac{1}{1}=\frac{1}{12}$

若删除的顺序为 $\{1,3,2\},\{3,1,2\}$, 那么概率为$\frac{1}{4} \times \frac{1}{3} \times \frac{1}{2}=\frac{1}{24}$

若删除的顺序为 $\{2,1,3\},\{2,3,1\}$, 那么概率为$\frac{1}{4} \times \frac{1}{2} \times \frac{1}{1}=\frac{1}{8}$

对于剩余的 $12$ 种删除了 $4$ 次的序列，概率为$\frac{1}{4} \times \frac{1}{3} \times \frac{1}{2} \times \frac{1}{1}=\frac{1}{24}$

容易发现答案即为 $\frac{2 \times 3}{12} + \frac{2 \times 3}{24}+\frac{2 \times 3}{8} + \frac{12 \times 4}{24}=\frac{7}{2}=3.50000$

数据范围

对于 $20\%$ 的数据, $n \leq 10$

对于 $60\%$ 的数据, $n \leq 10^5$

对于 $100\%$ 的数据, $n \leq 10^9,t \leq 100$

出题人善意的提醒

对于 C++ 选手，若对于正整数 $n,k$，希望得到 $\sqrt[k] n$，请尽量不要使用 C++ 自带的 $\operatorname{pow}$ 函数，以免可能产生不必要的精度误差。