题目描述

每个测试的时间限制：1 秒
每个测试的内存限制：256 兆字节

简单版与困难版的唯一区别在于数据范围。

有 $n$ 个孩子，每人正在读一本独特的书。每天结束时，第 $i$ 个孩子会把自己的书交给第 $p_i$ 个孩子（如果 $i = p_i$，则孩子把书留给自己）。保证所有的 $p_i$ 是 $1$ 到 $n$ 中互不相同的整数（即 $p$ 是一个排列）。$p$ 序列每天固定不变。

例如，如果 $n = 6$ 且 $p = [4,6,1,3,5,2]$，那么第一天结束时：

• 第 $1$ 个孩子的书会归第 $4$ 个孩子所有；
• 第 $2$ 个孩子的书会归第 $6$ 个孩子所有；
• 依此类推。

第二天结束时：

• 第 $1$ 个孩子的书会归第 $3$ 个孩子所有；
• 第 $2$ 个孩子的书会归第 $2$ 个孩子所有；
• 依此类推。

你的任务是，对于每个 $i$（$1$ 到 $n$），确定第 $i$ 个孩子的书第一次返回他本人手中是在第几天。

考虑以下例子：$p = [5,1,2,4,3]$。第 $1$ 个孩子的书的传递过程如下：

• 第 $1$ 天后，书在第 $5$ 个孩子手中；
• 第 $2$ 天后，书在第 $3$ 个孩子手中；
• 第 $3$ 天后，书在第 $2$ 个孩子手中；
• 第 $4$ 天后，书在第 $1$ 个孩子手中。

因此，经过第 $4$ 天后，第 $1$ 个孩子的书第一次返回本人手中。第 $4$ 个孩子的书则仅需 $1$ 天就返回。

你需要回答 $q$ 组独立的查询。

输入格式

第一行包含一个整数 $q$（$1 \le q \le 1000$）—— 查询的数量。接下来是 $q$ 组查询。

每组查询的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）—— 该查询中孩子的数量。
每组查询的第二行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$（$1 \le p_i \le n$，所有的 $p_i$ 互不相同，即 $p$ 是一个排列），表示第 $i$ 个孩子会把书交给第 $p_i$ 个孩子。

保证 $\sum n \le 2 \cdot 10^5$（所有查询的 $n$ 之和不超过 $2 \cdot 10^5$）。

输出格式

对于每组查询，输出一行 $n$ 个整数 $a_1, a_2, \dots, a_n$，其中 $a_i$ 表示该查询中第 $i$ 个孩子的书第一次返回他本人手中所需的天数。

6
5
1 2 3 4 5
3
2 3 1
6
4 6 2 1 5 3
1
1
4
3 4 1 2
5
5 1 2 4 3

1 1 1 1 1 
3 3 3 
2 3 3 2 1 3 
1 
2 2 2 2 
4 4 4 1 4