1 #include <iostream>
 2 #include <string.h>
 3 using namespace std;
 4 char s[200001];
 5 int next[200001];
 6 int c[200001];
 7 int ans;
 8 void GetNext(char t[],int next[])
 9 {
10     memset(c,0,sizeof(c));
11     int j,k;
12     j=0;k=-1;next[0] = -1;
13     int length;
14     for(length = 0;t[length]!=‘\0‘;length++);
15     while(j<length){
16         if(k==-1 || t[j]==t[k]){
17             if(k!=-1){
18                 c[j] = c[k] + 1;
19                 ans+=c[j];    
20             }
21             j++;k++;
22             next[j] = k;
23         }
24         else
25             k = next[k];
26     }
27 }
28 int main()
29 {
30     int T,n;
31     cin>>T;
32     while(T--){
33         cin>>n;
34         cin>>s;
35         ans = 0;
36         GetNext(s,next);
37         cout<<(ans+n)%10007<<endl;
38     }
39     return 0;
40 }