#include<bits/stdc++.h>
using namespace std;

#define int long long

const int N=1e4+1e3+7,P=998244353;

int qpow(int a,int b)
{
    int ret=1;
    while(b)
    {
        if(b&1)
            ret=ret*a%P;
        b>>=1;
        a=a*a%P;
    }
    return ret;
}

string s;

int son[N][26],tot,val[N];

int fail[N];

vector<int> g[N];

queue<int> q;

void dfs(int x)
{
    for(auto v:g[x])
        val[v]+=val[x],dfs(v);
}

double f[1001][N];

int pre[1001][N],pb[1001][N],pa[1001][N];

int n,m,ei,ex;

bool chk(double w)
{
    for(int i=1;i<=tot;i++)
        f[0][i]=-1e18;
    double ans=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=tot;j++)
            f[i][j]=f[i-1][j],pre[i][j]=j,pa[i][j]=0,pb[i][j]=0;
        int c=s[i-1]-'a';
        for(int j=0;j<=tot;j++)
        {
            int to=son[j][c];
            double W=f[i-1][j]-w+val[to];
            // ans=max(ans,W);
            if(W>ans)
                ans=W,ei=i,ex=to;
            if(W>f[i][to])
                f[i][to]=W,pre[i][to]=j,pa[i][to]=1,pb[i][to]=val[to];
        }
    }
    return ans>0;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin>>T;
    while(T--)
    {
        // cin>>n>>m;
        n=1000,m=40;
        s.clear();
        for(int i=1;i<=n;i++)
            s+=(char)(rand()%26+'a');
        // cin>>s;
        for(int i=0;i<=tot;i++)
            g[i].clear(),val[i]=0;
        tot=0;
        for(int j=0;j<26;j++)
            son[0][j]=-1;

        for(int i=1;i<=m;i++)
        {
            int x=0;
            string t;
            int w;
            for(int j=1;j<=100;j++)
                t+=(char)(rand()%26+'a');
            w=rand()%100000;
            // cin>>t>>w;
            for(auto c:t)
            {
                c-='a';
                if(son[x][c]==-1)
                {
                    son[x][c]=++tot;
                    for(int j=0;j<26;j++)
                        son[tot][j]=-1;
                }
                x=son[x][c];
            }
            val[x]+=w;
        }
        for(int i=0;i<26;i++)
            if(son[0][i]==-1)
                son[0][i]=0;
            else
                q.push(son[0][i]),fail[son[0][i]]=0;
        while(!q.empty())
        {
            int x=q.front();
            q.pop();
            for(int i=0;i<26;i++)
                if(son[x][i]==-1)
                    son[x][i]=son[fail[x]][i];
                else
                    q.push(son[x][i]),fail[son[x][i]]=son[fail[x]][i];
        }
        for(int i=1;i<=tot;i++)
            g[fail[i]].push_back(i);
        dfs(0);
        double l=0,r=1e8;
        for(int R=1;R<=60;R++)
        {
            double mid=(l+r)/2;
            if(chk(mid))
                l=mid;
            else
                r=mid;
        }
        // cout<<fixed<<setprecision(9)<<l<<"\n";
        int A=0,B=0;
        while(ei>0)
        {
            A+=pa[ei][ex];
            B+=pb[ei][ex];
            ex=pre[ei][ex];
            ei--;
        }
        // int g=__gcd(A,B);
        // A/=g,B/=g;
        // cout<<B<<"/"<<A<<"\n";
        cout<<B%P*qpow(A,P-2)%P<<"\n";
    }
}