转化一下问题，即为给定 \(n, a_{1, \cdots}\) 满足 \(\sum\limits a_i = n\)。
接下来可以花费 \(1\) 代价把 \(x = y + z\) 的 \(x\) 拆为 \(y\) 和 \(z\) 或者把 \(y\) 和 \(z\) 合并成 \(x\)。
求最后的 \(a'\) 的 \(\max\{\prod a'_i\}\) 和达成的最小代价。
首先对于第一问，就相当于是比较 \(x^y\) 和 \(y^x\) 的大小。
考虑取对数变为 \(y\ln x, x\ln y\)，同除 \(xy\) 就是 \(\frac{\ln x}{x}, \frac{\ln y}{y}\)。
然后考虑把 \(y = \frac{\ln x}{x}\) 函数图像画出来，发现对于 \(x\in \mathbb{N}_+\)，\(x = 3\) 时 \(y\) 最大，次大是 \(x = 2 / 4\)。
于是就可以知道，若 \(n\bmod 3 = 0\)，答案为 \(3^{\frac{n}{3}}\)；若 \(n\bmod 3 = 1\)，答案为 \(3^{\frac{n - 2}{3}}\times 2\)；若 \(n\bmod 3 = 1\)，答案为 \(3^{\frac{n - 4}{3}}\times 4\)。
然后考虑构造。
对于 \(n\bmod 3 = 0\) 的情况，不难发现就是直接贪心能拆 \(3\) 即拆 \(3\)。
对于剩下的 \(1\) 和 \(2\) 先合 \(1\) 和 \(2\) 再对于剩下的单独合。
正确性可以考虑证明其他的操作方式会比当前的操作方式劣。
然后是 \(n\bmod 3 = 2\)。
这个时候就需要多出来 \(1\) 个 \(2\) 消掉。
考虑到如果把 \(3\) 拆成 \(1, 2\) 其实还是不优（还剩了 \(2\) 显然不优，剩的全是 \(1\) 如果拿 \(2\) 去合并会劣 \(2\)，拿 \(1\) 去合并也会劣 \(2\)）。
对于那个 \(2\) 一定是用 \(2\) 更优其次才是 \(1, 1\) 合并（考虑只剩单独的 \(1, 2\) 的时候，\(1\) 的操作次数会带个 \(\frac{2}{3}\) 的系数，更优）。
最后是 \(n\bmod 3 = 1\)。
此时剩下的可以是 \(2\) 个 \(2\) 或者 \(1\) 个 \(4\)。
考虑到是 \(1\) 个 \(4\) 一定是要么直接消到 \(4\) 或者是 \(1, 3\) 合出来。
对于剩下的方案因为都 \(\le 2\) 所以肯定是合并成 \(2\) 个 \(2\) 更优。
还是相同的，能消 \(2\) 就消 \(2\)。
时间复杂度 \(O(n + \log P)\)。
#include<bits/stdc++.h>
using i64 = long long;
const i64 mod = 1e9 + 7;
inline i64 qpow(i64 a, i64 b) {
i64 v = 1;
while (b) b & 1 && ((v *= a) %= mod), b >>= 1, (a *= a) %= mod;
return v;
}
const int maxn = 1e6 + 10;
const int inf = 1e9;
int p[maxn], siz[maxn]; bool vis[maxn];
inline void solve() {
int n; scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &p[i]);
int m = 0;
for (int i = 1; i <= n; i++) vis[i] = 0;
for (int i = 1; i <= n; i++) {
if (vis[i]) continue;
siz[++m] = 0;
for (int j = i; ! vis[j]; j = p[j]) vis[j] = 1, siz[m]++;
}
if (n % 3 == 0) {
printf("%lld ", qpow(3, n / 3));
int cnt[3] = {0, 0, 0}, ans = 0;
for (int i = 1; i <= m; i++) {
if (siz[i] % 3 == 0) ans += siz[i] / 3 - 1;
else ans += siz[i] / 3;
cnt[siz[i] % 3]++;
}
if (cnt[1] >= cnt[2]) ans += cnt[2] + (cnt[1] - cnt[2]) / 3 * 2;
else ans += cnt[2];
printf("%d\n", ans);
} else if (n % 3 == 1) {
printf("%lld ", qpow(3, (n - 4) / 3) * 4 % mod);
int cnt1[3] = {0, 0, 0}, ans1 = 0;
bool f = 0;
for (int i = 1; i <= m; i++) {
if (siz[i] % 3 == 0) ans1 += siz[i] / 3 - 1;
else if (siz[i] % 3 == 1 && siz[i] > 1 && ! f) ans1 += (siz[i] - 4) / 3, f = 1;
else ans1 += siz[i] / 3, cnt1[siz[i] % 3]++;
}
if (f) {
if (cnt1[1] >= cnt1[2]) ans1 += cnt1[2] + (cnt1[1] - cnt1[2]) / 3 * 2;
else ans1 += cnt1[2];
} else ans1 = inf;
int cnt2[3] = {0, 0, 0}, ans2 = 0;
for (int i = 1; i <= m; i++) {
if (siz[i] % 3 == 0) ans2 += siz[i] / 3 - 1;
else ans2 += siz[i] / 3;
cnt2[siz[i] % 3]++;
}
int tot1 = 0, tot2 = 0;
if (cnt2[1] + cnt2[2] * 2 != n && cnt2[1]) {
tot1++, cnt2[1]--;
if (cnt2[1] >= cnt2[2]) tot1 += cnt2[2] + (cnt2[1] - cnt2[2]) / 3 * 2;
else tot1 += cnt2[2];
cnt2[1]++;
} else tot1 = inf;
if (cnt2[1] + cnt2[2] * 2 >= 4) {
if (cnt2[2] >= 2) {cnt2[2] -= 2;}
else if (cnt2[2] == 1) {cnt2[2] = 0, cnt2[1] -= 2, tot2++;}
else {cnt2[1] -= 4, tot2 += 2;}
if (cnt2[1] >= cnt2[2]) tot2 += cnt2[2] + (cnt2[1] - cnt2[2]) / 3 * 2;
else tot2 += cnt2[2];
} else tot2 = inf;
printf("%d\n", std::min(ans1, ans2 + std::min(tot1, tot2)));
} else {
printf("%lld ", qpow(3, (n - 2) / 3) * 2 % mod);
int cnt[3] = {0, 0, 0}, ans = 0;
for (int i = 1; i <= m; i++) {
if (siz[i] % 3 == 0) ans += siz[i] / 3 - 1;
else ans += siz[i] / 3;
cnt[siz[i] % 3]++;
}
cnt[2] ? (cnt[2]--) : (cnt[1] -= 2, ans++);
if (cnt[1] >= cnt[2]) ans += cnt[2] + (cnt[1] - cnt[2]) / 3 * 2;
else ans += cnt[2];
printf("%d\n", ans);
}
}
int main() {
int T; scanf("%d", &T);
while (T--) solve();
return 0;
}