根据传说,河内寺庙拥有从 $$$1$$$ 到 $$$n$$$ 的整数排列。寺庙前有一排颜色各异的石头。武僧可以对棋子进行如下操作:选择一个位置$$$i$$$ ($$$1 \le i \le n$$$),循环移动$$$i$$$、$$$p[i]$$$、$$$p[p[i]]$$$、...的棋子,即$$$i$$$位置的棋子会移动到$$$p[i]$$$位置,$$$p[i]$$$位置的棋子会移动到$$$p[i]$$$位置。 $$$p[i]$$$ 将移动到位置 $$$p[p[i]]$$$,依此类推,从位置 $$$j$$$ 开始的石头,使得 $$$p[j] = i$$$ 将移动到位置 $$$i$$$。
僧侣们每天必须使用任意数量的这些操作来获得新的石头排列。当所有可能的安排都完成时,世界就结束了。您想知道,如果可以在开始之前交换排列的某些元素会怎样?世界还能持续多少天?
您希望使用排列中两个元素的最少交换次数来获得一个排列,使世界能够尽可能长久地持续下去。
如果存在 $$$i$$$ 位置,使得该位置上的棋子颜色在这些排列中不同,则认为两种棋子排列不同。
输入
每个测试由多个测试用例组成。第一行包含测试用例的数量 $$$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$$$。
输出
对于每个 $$$t$$$ 测试用例,在新行中打印两个整数:世界可以持续的最大可能天数,以 $$$10^9 + 7$$$ 为模,以及所需的最小交换次数。
示例
输入 #1
3 3 2 3 1 3 2 1 3 3 1 2 3
输出 #1
3 0 3 1 3 2
输入 #2
5 4 2 3 4 1 4 2 3 1 4 4 2 1 4 3 4 2 1 3 4 4 1 2 3 4
输出 #2
4 0 4 1 4 0 4 1 4 2
注意
让我们用字母来标记石头的颜色。第一个示例的前两个测试用例的说明:
1. 利用排列$$$[2, 3, 1]$$$,我们还可以从ABC得到排列CAB和BCA。这已经是最大可能的结果了。
2. 利用排列$$$[2, 1, 3]$$$,可以从ABC得到唯一的BAC。正如我们在前面的例子中看到的,对于 $$$n = 3$$$,两种排列并不是不同排列的最大可能数量。例如,为了获得最佳排列,我们可以交换 $$$1$$$ 和 $$$3$$$,因此我们将得到排列 $$$[2, 3, 1]$$$。