CF1411F.The Thorny Path

According to a legend the Hanoi Temple holds a permutation of integers from $1$ to $n$. There are $n$ stones of distinct colors lying in one line in front of the temple. Monks can perform the following operation on stones: choose a position $i$ ($1 \le i \le n$) and cyclically shift stones at positions $i$, $p[i]$, $p[p[i]]$, .... That is, a stone from position $i$ will move to position $p[i]$, a stone from position $p[i]$ will move to position $p[p[i]]$, and so on, a stone from position $j$, such that $p[j] = i$, will move to position $i$.

Each day the monks must obtain a new arrangement of stones using an arbitrary number of these operations. When all possible arrangements will have been obtained, the world will end. You are wondering, what if some elements of the permutation could be swapped just before the beginning? How many days would the world last?

You want to get a permutation that will allow the world to last as long as possible, using the minimum number of exchanges of two elements of the permutation.

Two arrangements of stones are considered different if there exists a position $i$ such that the colors of the stones on that position are different in these arrangements.

据传说，河内寺庙中保存着一个 $1$ 到 $n$ 的整数排列 $p$。寺庙前有一排 $n$ 块颜色互不相同的石头。僧侣可以对石头执行如下操作：选择一个位置 $i$（$1 \le i \le n$），并对位置 $i$、$p[i]$、$p[p[i]]$、…… 上的石头进行循环移位。即：位于位置 $i$ 的石头移动到位置 $p[i]$，位于位置 $p[i]$ 的石头移动到位置 $p[p[i]]$，依此类推；而位于位置 $j$（满足 $p[j] = i$）的石头则移动到位置 $i$。

每天，僧侣必须通过任意次数的上述操作，得到一种新的石头排列。当所有可能的排列均已被获得时，世界将终结。你不禁思考：若能在初始时刻预先交换排列中若干个元素，世界又能延续多少天呢？

你希望找到一个排列，使得世界存续时间尽可能长，并且在达成该目标的前提下，交换两个元素的次数最少。

若存在某个位置 $i$，使得两种石头排列在该位置上的石头颜色不同，则称这两种排列为不同的排列。

Each test consists of multiple test cases. The first line contains the number of test cases $t$ ($1 \leq t \leq 10^3$). Description of the test cases follows.

The first line of each test case contains $n$ ($3 \leq n \leq 10^6$). The next line contains $n$ integers $p_1, \dots, p_n$ ($1 \le p_i \le n$). It is guaranteed that $p$ is a permutation.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \leq t \leq 10^3$）。随后是各测试用例的描述。

每个测试用例的第一行包含整数 $n$（$3 \leq n \leq 10^6$）。下一行包含 $n$ 个整数 $p_1, \dots, p_n$（$1 \le p_i \le n$）。保证 $p$ 是一个排列。

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

For each of the $t$ test cases, print two integers on a new line: the largest possible number of days the world can last, modulo $10^9 + 7$, and the minimum number of exchanges required for that.

对于每个测试用例，输出一行两个整数：世界可能持续的最长天数（对 $10^9 + 7$ 取模）以及达到该天数所需的最少交换次数。

Let's label the colors of the stones with letters. Explanations for the first two test cases of the first example:

1. Using the permutation $[2, 3, 1]$, we can additionally obtain the arrangements CAB and BCA from ABC. This is already the maximum possible result.
2. Using the permutation $[2, 1, 3]$, the only BAC can be obtained from ABC. As we saw in the previous case, two arrangements are not the maximum possible number of distinct arrangements for $n = 3$. To get an optimal permutation, for example, we can swap $1$ and $3$, so we will get the permutation $[2, 3, 1]$.

我们用字母来标记石头的颜色。第一个样例的前两个测试用例的解释如下：

1. 使用排列 $[2, 3, 1]$，我们可以从 ABC 额外得到排列 CAB 和 BCA。这已经是可能的最大结果。
2. 使用排列 $[2, 1, 3]$，仅能从 ABC 得到 BAC。如前一情况所示，两种排列并非 $n = 3$ 时所能得到的不同排列数的最大值。为获得最优排列，例如可交换 $1$ 和 $3$，从而得到排列 $[2, 3, 1]$。