#include<bits/stdc++.h>

using namespace std;

#define int long long

#define maxn 1000000+10

int P[maxn],g[maxn];

bool vis[maxn];

unordered_map<int,int> mp;

int T,n,k;

const int mod =(1e9+);

int cnt=;

void init()

{

    g[]=;

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

        g[i]=;

    }

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

    {

        //g[i]=1;

        if(!vis[i])

        {

            P[cnt++]=i;

            g[i]=(i*i-)%mod;

        }

        for(int j=; j<cnt&&(P[j]*i)<maxn; j++)

        {

            vis[i*P[j]]=;

            g[P[j]*i]=(g[P[j]]*g[i]%mod);

            if(i%P[j]==)

            {

                g[P[j]*i]=(g[i]*(P[j]*P[j])%mod)%mod;

                break;

            }

        }

    }

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

    {

        g[i]=(g[i]+g[i-]+mod)%mod;

    }

}

int qp(int x,int n)

{

    int ans=;

    while(n)

    {

        if(n&)

        {

            ans=(ans*x)%mod;

        }

        x=(x*x)%mod;

        n>>=;

    }

    return ans%mod;

}

int _k;

int Sum(int x,int n)

{

    if(x==)

    {

        return (_k-+mod)%mod;

    }

    else

    {

        return (((x*(qp(x,n)-+mod)%mod)%mod*qp((x-)%mod,mod-)%mod)%mod-x+mod)%mod;

    }

}

int Sum2(int n)

{

    int ans=qp(,mod-);

    ans=(ans*((n*(n+)%mod)%mod*(*n%mod+)%mod)%mod)%mod;

    return ans;

}

int G(int n)

{

    int ans=;

    int r;

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

    {

         r=n/(n/i);

        int x=n/i;

        if(x<maxn)

        {

            ans=(ans+g[x]*(r-i+))%mod;

        }

        else if(mp[x])

        {

            ans=(ans+mp[x]*(r-i+))%mod;

        }

        else ans=(ans+G(x)*(r-i+))%mod;

    }

    mp[n]=(Sum2(n)-ans+mod)%mod;

    return mp[n];

}

int cal(int x)

{

    if(x<maxn)return g[x];

    if(mp[x])return mp[x];

    return G(x);

}

char s[maxn];

signed main()

{

    init();

    int ans=;

    scanf("%lld",&T);

    //string s;

    while(T--)

    {

        ans=;

        scanf("%lld",&n);

        scanf("%s",s);

        k=;

        _k=;

        int _n=strlen(s);

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

        {

             _k=(_k*+s[i]-'')%(mod);

            k=((k*)+s[i]-'')%(mod-);

        }

        int r;

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

        {

            r=n/(n/i);

            ans=(ans+((Sum((n/i),k))%mod*(cal(r)-cal(i-)+mod)%mod)%mod)%mod;

        }

        cout<<ans<<'\n';

    }

}