#include<bits/stdc++.h>
#define endl '\n'
//#define int long long
#define INF=0x3f3f3f3f;//int类型的正无穷
#define LLINF=0x3f3f3f3f3f3f3f3f;//long long类型的正无穷

using namespace std;
typedef long long LL;
typedef pair<int,int> PII; 
typedef unsigned long long ULL;
const int M=2010;
const int P=131;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};

ULL h[N],p[N];
//h数组是前缀和数组,表示字符串的前缀值
//p数组用于存储p的多少次方(预处理出所有次方结果)

ULL get(int l,int r)//求[l,r]之间的哈希值
{
    return h[r]-h[l-1]*p[r-l+1];
}

int quick_mi(int a,int k,int p)//求快速幂 
{
    int res=1;
    while(k)
    {
        if(k&1)
        res=(LL)res*a%p;
        k>>=1;
        a=(LL)a*a%p;
    }
    return res;
}

int gcd(int a,int b)//求最大公约数
{
    return b?gcd(b,a%b):a;
}

void solve()
{
    p[0]=1;     //p的0次方等于1
    for(int i=1;i<=n;i++)   //预处理字符串哈希前缀
    {
        p[i]=p[i-1]*P;
        h[i]=h[i-1]*P+str[i];
    } 
}
signed main()
{
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
        int T; cin>>T;//询问次数
        while(T--)
        solve();
        return 0;       
}