G2. 中等恶魔问题（困难版）
时间限制：$2$ 秒
内存限制：$256$ MB

这是该问题的困难版本。两个版本之间的主要区别以粗体标出。

一群 $n$ 只蜘蛛聚集在一起交换毛绒玩具。初始时，每只蜘蛛有 $1$ 个毛绒玩具。每年，如果蜘蛛 $i$ 有至少一个毛绒玩具，它会将恰好一个毛绒玩具送给蜘蛛 $r_i$。否则，它什么也不做。注意所有毛绒玩具的转移同时发生。在这个版本中，允许每只蜘蛛在任何时刻拥有超过 $1$ 个毛绒玩具。

如果在当前年份，每只蜘蛛拥有的毛绒玩具数量（在当前年份交换之前）与前一年（前一年交换之前）相同，则过程是稳定的。注意第 $1$ 年永远不可能是稳定的。

找出过程第一次变得稳定的年份。

输入
第一行包含一个整数 $t$ ($1 \le t \le 10^4$) —— 测试用例的数量。
每个测试用例的第一行包含一个整数 $n$ ($2 \le n \le 2 \cdot 10^5$) —— 蜘蛛的数量。
接下来一行包含 $n$ 个整数 $r_1, r_2, \dots, r_n$ ($1 \le r_i \le n$, $r_i \ne i$) —— 每只蜘蛛送出毛绒玩具的目标。
保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

输出
对于每个测试用例，输出一行一个整数，表示过程第一次变得稳定的年份。

样例输入

5
2
2 1
5
2 3 4 5 1
5
2 1 4 2 3
5
4 1 1 5 4
10
4 3 9 1 6 7 9 10 10 3

样例输出

2
2
5
5
5

说明
对于第二个测试用例：
在第 $1$ 年，每只蜘蛛拥有的毛绒玩具数量如下：$[1,1,1,1,1]$。然后，第 $1$ 年的交换发生。
在第 $2$ 年，每只蜘蛛拥有的毛绒玩具数量如下：$[1,1,1,1,1]$。因为这个数组与前一年相同，所以这一年是稳定的。

对于第三个测试用例：
在第 $1$ 年，每只蜘蛛拥有的毛绒玩具数量如下：$[1,1,1,1,1]$。然后，第 $1$ 年的交换发生。
在第 $2$ 年，每只蜘蛛拥有的毛绒玩具数量如下：$[1,2,1,1,0]$。然后，第 $2$ 年的交换发生。
在第 $3$ 年，每只蜘蛛拥有的毛绒玩具数量如下：$[1,3,0,1,0]$。然后，第 $3$ 年的交换发生。
在第 $4$ 年，每只蜘蛛拥有的毛绒玩具数量如下：$[1,4,0,0,0]$。然后，第 $4$ 年的交换发生。
在第 $5$ 年，每只蜘蛛拥有的毛绒玩具数量如下：$[1,4,0,0,0]$。因为这个数组与前一年相同，所以这一年是稳定的。