G2. Medium Demon Problem (hard version)
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is the hard version of the problem. The key difference between the two versions is highlighted in bold.

A group of $$$n$$$ spiders has come together to exchange plushies. Initially, each spider has $$$1$$$ plushie. Every year, if spider $$$i$$$ has at least one plushie, he will give exactly one plushie to spider $$$r_i$$$. Otherwise, he will do nothing. Note that all plushie transfers happen at the same time. In this version, each spider is allowed to have more than 1 plushie at any point in time.

The process is stable in the current year if each spider has the same number of plushies (before the current year's exchange) as he did the previous year (before the previous year's exchange). Note that year $$$1$$$ can never be stable.

Find the first year in which the process becomes stable.

Input

The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.

The first line of each test case contains an integer $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$) — the number of spiders.

The following line contains $$$n$$$ integers $$$r_1, r_2, \ldots, r_n$$$ ($$$1 \leq r_i \leq n, r_i \neq i$$$) — the recipient of the plushie of each spider.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output an integer on a new line, the first year in which the process becomes stable.

Example
Input
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
Output
2
2
5
5
5
Note

For the second test case:

  • At year $$$1$$$, the following array shows the number of plushies each spider has: $$$[1, 1, 1, 1, 1]$$$. Then, year $$$1$$$'s exchange happens.
  • At year $$$2$$$, the following array shows the number of plushies each spider has: $$$[1, 1, 1, 1, 1]$$$. Since this array is the same as the previous year, this year is stable.

For the third test case:

  • At year $$$1$$$, the following array shows the number of plushies each spider has: $$$[1, 1, 1, 1, 1]$$$. Then, year $$$1$$$'s exchange happens.
  • At year $$$2$$$, the following array shows the number of plushies each spider has: $$$[1, 2, 1, 1, 0]$$$. Then, year $$$2$$$'s exchange happens.
  • At year $$$3$$$, the following array shows the number of plushies each spider has: $$$[1, 3, 0, 1, 0]$$$. Then, year $$$3$$$'s exchange happens.
  • At year $$$4$$$, the following array shows the number of plushies each spider has: $$$[1, 4, 0, 0, 0]$$$. Then, year $$$4$$$'s exchange happens.
  • At year $$$5$$$, the following array shows the number of plushies each spider has: $$$[1, 4, 0, 0, 0]$$$. Since this array is the same as the previous year, this year is stable.