#include <bits/stdc++.h> using namespace std; int T,n,a[100005]; int b[100005]; int sz[100005]; int d[100005]; int f[100005]; bool vis[100005]; vector <int> r,s[100005]; vector <int> vec[100005]; signed main () { freopen("a.in","r",stdin); freopen("a.out","w",stdout); cin >> T; while (T--) { cin >> n; for (int i = 1;i <= n;i++) { cin >> a[i]; s[a[i]].push_back(i); } for (int i = 1;i <= n;i++) { if (b[i]) { continue; } for (int u = i;;u = a[u]) { if (b[u] == i) { r.push_back(u); } if (b[u]) { break; } b[u] = i; } } queue <int> q; for (auto i : r) { d[i] = 0; sz[i] = 1; for (int u = a[i];u != i;u = a[u]) { sz[i]++; } d[a[i]] = sz[i] - 1; for (int u = a[i];u != i;u = a[u]) { if (a[u] != i) { d[a[u]] = (d[u] + sz[i] - 1) % sz[i]; } } q.push(i); vis[i] = 1; f[i] = i; for (int u = a[i];u != i;u = a[u]) { sz[u] = sz[i]; q.push(u); vis[u] = 1; f[u] = i; } for (int j = 0;j < sz[i];j++) { vec[i].push_back(1); } } while (!q.empty()) { int u = q.front(); q.pop(); for (auto v : s[u]) { if (!vis[v]) { sz[v] = sz[u]; d[v] = (d[u] + 1) % sz[v]; f[v] = f[u]; vec[f[v]][d[v]]++; q.push(v); } } } long long ans = 1ll * n * (n - 1) / 2; for (int i = 1;i <= n;i++) { if (f[i] == i) { for (int j = 0;j < sz[i];j++) { long long x = vec[i][j]; ans -= x * (x - 1) / 2; } } } cout << ans << endl; r.clear(); for (int i = 1;i <= n;i++) { vec[i].clear(); s[i].clear(); b[i] = 0; d[i] = 0; f[i] = 0; sz[i] = 0; vis[i] = 0; } } return 0; }