# include <cstdio>

 # include <cstring>

 using namespace std;

 char S[] ;

 int next[] ;

 int dp[] ;

 int len ;

 void getNext()

 {

     int j, k;

     j = ; k = -; next[] = -;

     while(j < len)

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

             next[++j] = ++k;

         else

             k = next[k];

 }

 int main ()

 {

     int T ;

     scanf("%d" , &T);

     while (T--)

     {

         scanf("%d" , &len) ;

         scanf("%s" , S) ;

         getNext() ;

         dp[] =  ;

         int ans =  ;

         int i ;

         for (i =  ; i<= len ; i++)

         {

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

             dp[i] %=  ;

             ans += dp[i] ;

             ans %=  ;

         }

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

     }

     return  ;

 }