D. Тернистый путь
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Легенда гласит, что в Ханойском храме хранится перестановка чисел от $$$1$$$ до $$$n$$$. Перед храмом в линию лежат $$$n$$$ разноцветных камней. Жрецы могут проводить следующую операцию над камнями: выбрать позицию $$$i$$$ ($$$1 \le i \le n$$$) и циклически сдвинуть камни на позициях $$$i$$$, $$$p[i]$$$, $$$p[p[i]]$$$, .... То есть, камень с позиции $$$i$$$ перейдет на позицию $$$p[i]$$$, камень с позиции $$$p[i]$$$ перейдет на позицию $$$p[p[i]]$$$, и т.д., на позицию $$$i$$$ перейдет камень с позиции $$$j$$$, такой что $$$p[j] = 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$$$ и минимальное количество необходимых для этого обменов.

Примеры
Входные данные
3
3
2 3 1
3
2 1 3
3
1 2 3
Выходные данные
3 0
3 1
3 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
Выходные данные
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]$$$.