//hdu 3336
//Answer 好孩子
//刚刚思想是采用KMP+DP的递推；前1—next[i]与后面next[i]—i-1刚刚好相等
//这个就在前面的基础上加一代表前i-1个为前最的最大重复数；
//思路是next[]数组总体往后移一位；

就像：abcdabcd;

next[]:

-1 0 0 0 0 1 1 1 1

后移一位：
0 0 0 0 1 1 1 1

刚刚好对应字符下表看成是1开始的每一位：
//状态方程：cont[i]=cont[next[i]]+1;
//本题就是把所有的cont[]加起来；
#include<iostream>
using namespace std;

const int T=300000;
const int size=10007;

int next[T],cont[T],len;
char a[T];

void getnext(){
 int i,j;
 next[0]=-1;i=0;j=-1;
 while(i<len){
  if(j==-1 || a[i]==a[j]){
   i++;
   j++;
   next[i]=j;
  }
  else j=next[j];
 }
}

//dp
int Gram(){
 int i,sum=0;
 memset(cont,0,sizeof(cont));
 for(i=1;i<=len;i++){
  cont[i]=(cont[next[i]]+1)%size;  //前缀i的相等加一；
  sum=(sum+cont[i])%size;
 }
 return sum;
}

int main(){
 int R;
 freopen("in.txt","r",stdin);
 freopen("out.txt","w",stdout);
 cin>>R;while(R--){
  cin>>len;
  cin>>a;
  getnext();
  int sum=Gram();
  cout<<sum<<endl;
 }
 return 0;
}