#include <cstdio>

 #include <cctype>

 #define M 10007

 #define maxn 200010

 int n;

 char aa[maxn];

 int f[maxn], dp[maxn];

 void gn( int &v ) {

     char ch, opt;

     while(!isdigit(ch=getchar())) opt=ch;

     v=ch-'';

     while( isdigit(ch=getchar())) v=v*+ch-'';

     if( opt=='-' ) v=-v;

 }

 void gc( char &ch ) {

     while(!isalpha(ch=getchar()));

 }

 void getfail() {

     f[] = f[] = ;

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

         j = f[i];

         while( j && aa[i]!=aa[j] ) j=f[j];

         f[i+] = aa[i]==aa[j] ? j+ : ;

     }

 }

 int main() {

     int T;

     gn(T);

     while( T-- ) {

         gn(n);

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

             gc(aa[i]);

         getfail();

         int sum=;

         dp[] = dp[] = ;

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

             dp[i] = dp[f[i]]+(f[i]!=);

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

         }

         sum += n;

         sum %= M;

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

     }

 }