#include<bits/stdc++.h>

 using namespace std;

 typedef unsigned int ui;

 typedef long long ll;

 typedef unsigned long long ull;

 #define pf printf

 #define mem(a,b) memset(a,b,sizeof(a))

 #define prime1 1e9+7

 #define prime2 1e9+9

 #define pi 3.14159265

 #define lson l,mid,rt<<1

 #define rson mid+1,r,rt<<1|1

 #define scand(x) scanf("%llf",&x)

 #define f(i,a,b) for(int i=a;i<=b;i++)

 #define scan(a) scanf("%d",&a)

 #define dbg(args) cout<<#args<<":"<<args<<endl;

 #define inf 0x3f3f3f3f

 #define maxn 1000010

 int n,m,t;

 int nxt[maxn];

 char s[maxn];

 void getnxt()

 {

     int i=-,j=;

     nxt[]=-;

     while(j<n)

     {

         if(i==-||s[i]==s[j])

         {

             i++,j++;

             nxt[j]=i;//不能用kmp优化的nxt，那样会损失数量

         }

         else i=nxt[i];

     }

 }

 int main()

 {

     //freopen("input.txt","r",stdin);

     //freopen("output.txt","w",stdout);

     std::ios::sync_with_stdio(false);

     scan(t);

     while(t--)

     {

         scan(n);

         scanf("%s",s);

         getnxt();

         int ans=;

         f(i,,n)//查看以i-1为截至位置的公共前缀后缀

         {

             int j=i;

             while(j>)

             {

                 ans++;//初始时本身还要算一次

                 if(ans>)ans-=;

                 j=nxt[j];

             }

         }

         pf("%d\n",ans);

     }

  } 

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <time.h>

 #include <cstdlib>

 #include <cmath>

 #include <algorithm>

 using namespace std;

 int const MOD = ;

 int const MAXN = ;

 char s[MAXN];

 int next[MAXN],dp[MAXN];

 inline void Get_Next(int n){

     memset(next,,sizeof(next));

     for(int i = ;i < n;i++){

         int j = next[i];

         while(j && s[i] != s[j]) j = next[j];

         if(s[i] == s[j]) next[i + ] = j + ;

         else next[i + ] = ;

     }

 }

 int main(){

     int T;

     while(~scanf("%d",&T)){

         while(T--){

             int n;

             scanf("%d",&n);

             scanf("%s",s);

             Get_Next(n);

             for(int i = ;i < n;i++){

                 dp[i] = ;

             }

             dp[] = ;

             int sum = ;

             for(int i = ;i <= n;i++){

                 dp[i] = dp[next[i]] + ;

                 sum = (sum + dp[i]) % MOD;

             }

             printf("%d\n",sum);

         }

     }

     return ;

 }