A93509.排列轮转排序

给定一个长度为 $n$ 的排列 $a$。我们称下标 $i$ 是“好”的，如果满足 $a_i=i$。

每经过 $1$ 秒钟，我们将所有不是“好”的下标对应的元素整体向右轮转一位。具体来说：

• 设 $s_1,s_2,\dots,s_k$ 是所有不是“好”的下标，按从小到大排列；
• 对于每个 $i$ 从 $1$ 到 $k$，同时执行 $a_{s_{(i\bmod k)+1}} := a_{s_i}$。（也就是这些位置的值整体右移一格）

请你对每个 $i$（$1\le i\le n$），求出下标 $i$ 第一次变为“好”（即第一次出现 $a_i=i$）的时刻（从 $0$ 秒开始计时）。

排列：由 $1$ 到 $n$ 的 $n$ 个互不相同的整数组成的数组。

第一行一个整数 $t$（$1\le t\le 10^4$），表示测试用例数量。

每个测试用例：

• 第一行一个整数 $n$（$1\le n\le 10^6$）
• 第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$，表示一个排列（$1\le a_i\le n$）

保证所有测试用例中 $n$ 的总和不超过 $10^6$。

对每个测试用例，输出一行 $n$ 个整数，第 $i$ 个整数表示下标 $i$ 第一次变为“好”的时刻。

样例解释

• 第一个用例里，$2$ 和 $5$ 一开始就满足 $a_2=2,a_5=5$，所以它们答案是 $0$；其余位置在第 $1$ 秒一起轮转后都变好。
• 第二个用例里，$5$ 一开始就是好下标；之后每秒对“不好”的下标集合轮转，分别在第 $1$ 秒、第 $2$ 秒让更多位置变好。