定义对正整数多重集 $K$ 的一次整体分裂（mass split）操作：对于多重集中的每个整数 $k_i$，我们将其替换为数对 $d_i$ 和 $k_i / d_i$，其中 $d_i$ 是 $k_i$ 的一个随机正整数因数，且满足 $d_i > 1$ 且 $d_i < k_i$。如果 $k_i$ 是质数，则保持不变。所有满足条件的因数被选择的概率均等。

例如，假设多重集为 $\{2, 10, 12, 12\}$。那么第一次整体分裂后可能得到的多重集为 $\{2, 2, 3, 3, 4, 4, 5\}$、$\{2, 2, 2, 3, 4, 5, 6\}$ 和 $\{2, 2, 2, 2, 5, 6, 6\}$（第一种和第三种情况的概率为 $0.25$，第二种情况的概率为 $0.5$）；而第二次整体分裂后，唯一可能得到的多重集为 $\{2, 2, 2, 2, 2, 2, 3, 3, 5\}$。

如果我们从一个仅包含单个整数 $N$ 的多重集开始，求将其分裂为仅包含质数的多重集所需的期望整体分裂次数。期望次数为所有可能值的概率加权平均值。

输入格式

输入的第一行包含一个整数 $T$（$1 \le T \le 10^4$），表示测试用例的数量。

每个测试用例包含一个整数 $N$（$2 \le N \le 10^{10}$），表示初始多重集中的唯一元素。

输出格式

对于每个测试用例，输出一个实数，表示期望的整体分裂次数。与真实值的绝对误差或相对误差不超过 $10^{-6}$。

样例

输入样例 1

3
3
12
48

输出样例 1

0
2.0
3.3333333