#include <cstdio>

 #include <cstring>

 const int maxn =  + ;

 const int MOD = ;

 char s[maxn];

 int next[maxn], l;

 void get_next()

 {

     int k = -, j = ;

     next[] = -;

     while(j < l)

     {

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

         {

             k++;

             j++;

             next[j] = k;

         }

         else k = next[k];

     }

 }

 int main(void)

 {

     int T;

     scanf("%d", &T);

     while(T--)

     {

         scanf("%d", &l);

         scanf("%s", s);

         get_next();

         int ans = ;

         for(int j = ; j < l; ++j)

             if(next[j] >  && next[j] +  != next[j+])

                 ans = (ans + next[j]) % MOD;

         ans = (ans + l + next[l]) % MOD;

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

     }

     return ;

 }