#include<bits/stdc++.h> using namespace std; #define int long long #define pb push_back #define sc second const int N=1e5+10; int T,n,ans,a[N],deg[N],dis[N]; queue<int>q; vector<int>e[N]; void dfs(int u,int sz,map<int,int> &mp){ mp[dis[u]]++;//cout<<"!!!"<<u<<" "<<dis[u]<<" "<<mp[dis[u]]<<endl; for(int v:e[u]){dis[v]=(dis[u]+1)%sz;dfs(v,sz,mp);} } inline void init(){ for(int i=0;i<=N-5;i++){deg[i]=0;dis[i]=0;e[i].clear();} } signed main(){ scanf("%lld",&T); while(T--){ init(); scanf("%lld",&n); for(int i=1;i<=n;i++){scanf("%lld",&a[i]);deg[a[i]]++;} for(int i=1;i<=n;i++){if(!deg[i])q.push(i);} while(!q.empty()){ int u=q.front();q.pop(); deg[a[u]]--;e[a[u]].pb(u); if(!deg[a[u]])q.push(a[u]); } // for(int i=1;i<=n;i++)cout<<deg[i]<<" ";cout<<endl; ans=n*(n-1)/2; for(int i=1;i<=n;i++){ if(deg[i]){//一定是环上的点 vector<int>ring; map<int,int>mp; for(int u=i;deg[u];u=a[u]){ // cout<<"!!"<<u<<" "<<a[u]<<" "<<deg[a[u]]<<endl; ring.pb(u); dis[u]=ring.size()-1;//cout<<u<<" "<<ring.size()<<endl; deg[u]=0; }//cout<<"???"<<endl; for(int u:ring){ // cout<<u<<" "; dis[u]=(ring.size()-dis[u])%ring.size(); dfs(u,ring.size(),mp); }//cout<<endl; for(auto x:mp){ans-=x.sc*(x.sc-1)/2;} } } printf("%lld\n",ans); } return 0; }