/*input
2
3
1 2 3
3
2 3 1

*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;
using pii=pair<int,int>;
#define f first
#define s second
#define pb push_back
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define FILL(n,x) memset(n,x,sizeof(n))
#define ALL(_a) _a.begin(),_a.end()
#define sz(x) (int)x.size()
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()),c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
const ll maxn=5e5+5;
const ll maxlg=__lg(maxn)+2;
const ll INF64=4e18;
const int INF=0x3f3f3f3f;
const int MOD=998244353;
const ld PI=acos(-1);
const ld eps=1e-4;
#define lowb(x) x&(-x)
#define MNTO(x,y) x=min(x,(__typeof__(x))y)
#define MXTO(x,y) x=max(x,(__typeof__(x))y)
template<typename T1,typename T2>
ostream& operator<<(ostream& out,pair<T1,T2> P){
    out<<P.f<<' '<<P.s;
    return out;
}
template<typename T>
ostream& operator<<(ostream& out,vector<T> V){
    REP(i,sz(V)) out<<V[i]<<((i!=sz(V)-1)?" ":"");
    return out;
}
ll mult(ll a,ll b){
    return a*b%MOD;
}
ll mypow(ll a,ll b){
    a%=MOD;
    if(a==0) return 0;
    if(b<=0) return 1;
    ll res=1LL;  
    while(b){
        if(b&1) res=(res*a)%MOD;
        a=(a*a)%MOD;
        b>>=1;
    }
    return res;
}
int arr[maxn];
int vis[maxn];
multiset<int> mx[maxn];
int lpf[maxn];
int cnt[maxn];
int inv[maxn];
ll ans=1;
void add(int x){
    while(x>1){
        int z=lpf[x];
        int c=0;
        while(x%z==0){
            x/=z;
            ++c;
        }
        int pv=(*prev(mx[z].end()));
        mx[z].insert(c);
        if(c<=pv) continue;
        ans=ans*mypow(z,c-pv);
    }
}
void del(int x){
    while(x>1){
        int z=lpf[x];
        int c=0;
        int stf=1;
        while(x%z==0){
            x/=z;
            stf*=z;
            ++c;
        }
        ans=ans*inv[stf]%MOD;
        mx[z].erase(mx[z].find(c));
        int k=(*prev(mx[z].end()));
        ans=ans*mypow(z,k)%MOD;
    }
}
void solve(){
    int n;
    cin>>n;
    REP(i,n){
        cin>>arr[i],--arr[i];
        mx[i+1].insert(0);
    }
    int cur=1;
    vector<int> v;
    REP(i,n){
        if(vis[i]) continue;
        int x=i;
        int len=0;
        while(!vis[x]){
            vis[x]=cur;
            x=arr[x];
            ++len;
        }
        cnt[len]++;
        v.pb(len);
        add(len);
        ++cur;
    }
    SORT_UNIQUE(v);
    ll tot=0;
    REP(i,sz(v)){
        del(v[i]);
        for(int j=i+1;j<sz(v);j++){
            del(v[j]);
            add(v[i]+v[j]);
            tot+=ans*2*cnt[v[i]]%MOD*cnt[v[j]]%MOD*v[i]%MOD*v[j]%MOD;
            del(v[i]+v[j]);
            add(v[j]);
        }
        if(cnt[v[i]]>1){
            del(v[i]);
            add(2*v[i]);
            tot+=ans*cnt[v[i]]%MOD*(cnt[v[i]]-1)%MOD*v[i]%MOD*v[i]%MOD;

            del(2*v[i]);
            add(v[i]);
        }
        tot%=MOD;
    }
    cout<<tot<<'\n';
    REP(i,n) vis[i]=0,mx[i+1].clear(),cnt[i+1]=0;
}
int main(){
    for(int i=2;i<maxn;i++){
        for(int j=i;j<maxn;j+=i){
            if(!lpf[j]) lpf[j]=i;
        }

    }
    REP1(i,maxn-1) inv[i]=mypow(i,MOD-2);
    int t;
    cin>>t;
    while(t--) solve();
}