#include <map>

#include <set>

#include <list>

#include <cmath>

#include <queue>

#include <stack>

#include <cstdio>

#include <vector>

#include <string>

#include <cctype>

#include <complex>

#include <cassert>

#include <utility>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

using namespace std;

typedef pair<int,int> PII;

typedef long long ll;

#define lson l,m,rt<<1

#define pi acos(-1.0)

#define rson m+1,r,rt<<11

#define All 1,N,1

#define read freopen("in.txt", "r", stdin)

#define N 200010

const ll  INFll = 0x3f3f3f3f3f3f3f3fLL;

const int INF= 0x7ffffff;

const int mod =  ;

int dp[N],f[N],n;

char str[N];

void getnext(){

    int i=,j=-;

    f[]=-;

    while(i<n){

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

        {

            i++;j++;

            f[i]=j;

        }

        else j=f[j];

    }

}

void solve(){

    getnext();

        //cout<<1<<endl;

    memset(dp,,sizeof(dp));

    int total=;

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

        dp[i]=(dp[f[i]]+)%mod;

        total=(total+dp[i])%mod;

    }

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

}

int main()

{

    int t;

    scanf("%d",&t);

    while(t--){

        scanf("%d",&n);

        scanf("%s",str);

        solve();

    }

return ;

}