#include <bits/stdc++.h>
using namespace std;
#define mod 10007
const int maxn=2e5+7;
int f[maxn];
char s[maxn];
void getfail(char *T)
{
    int i=1,j=0,n=strlen(T+1);f[1]=0;
    while(i<n){
        if(j==0||T[i]==T[j])//确定当前位，给下一位一个机会
            ++i,++j,f[i]=j;
        else
            j=f[j];
    }
}
int main()
{
    int T,n;
    cin>>T;
    while(T--)
    {
        scanf("%d%s",&n,s+1);
        getfail(s);
        int cnt=0;
        for(int i=1;i<=n;i++){
            int t=0;
            for(int j=i;j;j=f[j])
                if(s[i]==s[j]) // 相等才累加;
                    ++t;
            cnt=(cnt+t)%mod;
        }
        cout<<cnt<<endl;
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+7;
const int mod = 10007;
char p[N];
int f[N],dp[N];
void getfail()
{
    int j=0,n=strlen(p+1);
    f[1]=0;
    for(int i = 2;i <= n;i++){
       while(j && p[j+1] != p[i]) j = f[j];//确定当前位置是前面前缀串的最后一位；
       if(p[i] == p[j+1]) j++;
       f[i] = j;
    }
}
int main()
{
    int n,T;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        scanf("%s", p+1);
        getfail();
        int ans = 0;
        dp[0] = 0;
        for(int i = 1;i <= n;i++){
            dp[i] = dp[f[i]] + 1;
            ans = (ans+dp[i])%mod;
        }
        printf("%d\n",ans);
    }
    return 0;
}