Легенда гласит, что в Ханойском храме хранится перестановка чисел от \(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\) тестовых случаев в новой строке выведите два целых числа: наибольшее возможное количество дней, которые может просуществовать мир, по модулю \(10^9 + 7\) и минимальное количество необходимых для этого обменов.