SP8661 CHEFFEB - Bogosort

Johnny 最近学习了一个叫做「Bogosort」的排序算法。他觉得这种算法效率极低，因此想要改进一下。你可能知道，这个算法的基本思路是不断随机打乱序列，直到序列变得有序为止。但 Johnny 认为，每次打乱整个序列并不必要。如果在最后一次打乱之后，序列的前几个元素已经排好位置，那就将这些元素固定，不再参与后续打乱。对于后几个已经正确排列的元素也同样处理。例如，初始序列为 (3, 5, 1, 6, 4, 2)，经过一次打乱后得到 (1, 2, 5, 4, 3, 6)，这时他会固定住 1, 2 和 6，然后继续用相同的算法对剩下的 (5, 4, 3) 进行排序。Johnny 希望这样的优化可以大幅提高算法效率。你的任务是帮助他计算，在每个元素初始位置都错误的情况下，这个改进算法对前 $n$ 个自然数进行排序需要的平均打乱次数。

输入的第一行是一个整数 $t$，表示测试用例的数量。接下来的 $t$ 行每行包含一个整数 $n$，表示需要排序的自然数的数量。

对于每个测试用例，输出排序前 $n$ 个自然数所需的平均打乱次数，结果须用最简分数表示。 **本翻译由 AI 自动生成**