归并排序（Merge sort）算法按以下方式对一个包含 $n$ 个数字的数组进行排序。当 $n=1$ 时，我们不做任何操作。否则，我们将数组分成两半：前半部分包含前 $\lfloor \frac{n}{2} \rfloor$ 个元素，后半部分包含剩余的所有元素。然后，我们递归地对这两半进行排序。最后，我们将排好序的两半合并。

合并的过程如下：我们比较两半的第一个元素。较小的一个是整个数组中最小的元素，因此我们将其写入输出并从其所在的那一半中剔除。然后，我们取（剩余的）两半中的第一个元素，依此类推。一旦其中一半变为空，我们就不需要再进行任何比较，因为我们可以直接将另一半剩余的元素复制到输出中。为简单起见，我们假设所有元素都是不同的。

当对一个随机的 $n$ 元素排列进行排序时，该算法平均会进行多少次比较？

输入格式

输入文件的第一行包含一个整数 $t$ ($1 \le t \le 50000$)，表示测试用例的数量。接下来的 $t$ 行，每行包含一个整数 $n$ ($1 \le n \le 10^9$)。所有测试用例中的 $n$ 均不相同。

输出格式

输出 $t$ 行，每行一个浮点数，表示对应 $n$ 的平均比较次数。如果你的答案与正确答案的相对误差或绝对误差在 $10^{-9}$ 以内，则被视为正确。

样例

样例输入 1

2
3
5

样例输出 1

2.6666666667
7.1666666667