SP6981 RNDORDER - The Least Number

给定 $n$ 个符号：$a_1, a_2, \ldots, a_n$。已知这些符号有一个确定的顺序关系，即存在一个排列 $[P_1, P_2, \ldots, P_n]$ 满足 $a_{P_1} < a_{P_2} < \ldots < a_{P_n}$。我们希望通过一系列比较来推断出这个顺序关系。比较的过程如下： - 比较 $[a_1, a_2]$ - 比较 $[a_2, a_3]$，然后比较 $[a_1, a_3]$ - 比较 $[a_3, a_4]$，再比较 $[a_2, a_4]$，然后 $[a_1, a_4]$ - ... - 最后，比对 $[a_{n-1}, a_n]$，接着是 $[a_{n-2}, a_n]$，一直到 $[a_1, a_n]$ 注意，比较的先后顺序按照如上所列固定进行。例如，只有在完成 $[a_2, a_3]$ 的比较之后，才会进行 $[a_1, a_3]$ 的比较。 比较 $[a_i, a_j]$（其中 $i < j$）的定义如下： - 如果结果为 $1$，则表示 $a_i > a_j$；如果结果为 $-1$，则表示 $a_i < a_j$。 - 比较是一致的。例如，如果通过先前的比较已经确定 $a_2 < a_6$（可能因为 $a_2 < a_5$ 并且 $a_5 < a_6$），那么比较 $[a_2, a_6]$ 时会直接得到结果 $-1$。 - 如果 $a_i$ 和 $a_j$ 的关系在之前未知，则比较结果为 $1$ 和 $-1$ 的概率均为 $1/2$。 你的任务是计算出 $a_1$ 作为最终排序中最小元素的概率。

第一行输入一个整数 $T$，表示测试用例的数量。 接下来的 $T$ 行中，每行包含一个整数 $n$（$1 \leq n \leq 1000$）。

输出共 $T$ 行，每行给出一个测试用例的结果：即 $a_1$ 成为最小元素的概率。答案的精度要求是在误差不超过 $10^{-9}$ 的范围内视为正确。

- $1 \leq T \leq 1000$ - $1 \leq n \leq 1000$ **本翻译由 AI 自动生成**