/*************************************************************************
    > File Name: hdu3336.cpp
    > Author: ALex
    > Mail: 405045132@qq.com 
    > Created Time: 2015年01月04日 星期日 17时27分46秒
 ************************************************************************/

#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
/*************************************************************************
    > File Name: hdu1011.cpp
    > Author: ALex
    > Mail: 405045132@qq.com 
    > Created Time: 2015年01月03日 星期六 14时41分19秒
 ************************************************************************/

#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int mod = 10007;
const int N = 200010;
int next[N];
char str[N];
int dp[N];

void get_next()
{
	int len = strlen(str);
	int k = -1;
	int j = 0;
	next[0] = -1;
	while (j < len)
	{
		if (k == -1 || str[j] == str[k])
		{
			++k;
			++j;
			next[j] = k;
		}
		else
		{
			k = next[k];
		}
	}
}

int main()
{
	int t;
	int len;
	scanf("%d", &t);
	while (t--)
	{
		scanf("%d", &len);
		scanf("%s", str);
		get_next();
		for (int i = 1; i <= len; ++i)
		{
			dp[i] = 1;
		}
		dp[0] = 0;
		int ans = 0;
		for (int i = 1; i <= len; ++i)
		{
			dp[i] = dp[next[i]] + 1;
			dp[i] %= mod;
			ans += dp[i];
			ans %= mod;
		}
		printf("%d\n", ans);
	}
	return 0;
}