Problem Description

Uncle Mao is a wonderful ACMER. One day he met an easy problem, but Uncle Mao was so lazy that he left the problem to you. I hope you can give him a solution.
Given a string s, we define a substring that happens exactly k times as an important string, and you need to find out how many substrings which are important strings.

 

Input

The first line contains an integer T (T≤100) implying the number of test cases.
For each test case, there are two lines:
the first line contains an integer k (k≥1) which is described above;
the second line contain a string s (length(s)≤105).
It's guaranteed that ∑length(s)≤2∗106.

∑length(s)≤2∗106.

 

Output

For each test case, print the number of the important substrings in a line.

 

Sample Input

 

Sample Output

#include <stdio.h>

#include <algorithm>

#include <cstdlib>

#include <cstring>

#include <bitset>

#include <string>

#include <stack>

#include <cmath>

#include <queue>

#include <set>

#include <map>

using namespace std;

#define INF 0x3f3f3f3f

#define LC(x) (x<<1)

#define RC(x) ((x<<1)+1)

#define MID(x,y) ((x+y)>>1)

#define fin(name) freopen(name,"r",stdin)

#define fout(name) freopen(name,"w",stdout)

#define CLR(arr,val) memset(arr,val,sizeof(arr))

#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);

typedef pair<int, int> pii;

typedef long long LL;

const double PI = acos(-1.0);

const int N = 100010;

int wa[N], wb[N], sa[N], cnt[N];

char s[N];

int height[N], ran[N], dp[N][18];

int len;

inline int cmp(int r[], int a, int b, int d)

{

    return r[a] == r[b] && r[a + d] == r[b + d];

}

void DA(int n, int m)

{

    int i;

    int *x = wa, *y = wb;

    for (i = 0; i < m; ++i)

        cnt[i] = 0;

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

        ++cnt[x[i] = s[i]];

    for (i = 1; i < m; ++i)

        cnt[i] += cnt[i - 1];

    for (i = n - 1; i >= 0; --i)

        sa[--cnt[x[i]]] = i;

    for (int k = 1; k <= n; k <<= 1)

    {

        int p = 0;

        for (i = n - k; i < n; ++i)

            y[p++] = i;

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

            if (sa[i] >= k)

                y[p++] = sa[i] - k;

        for (i = 0; i < m; ++i)

            cnt[i] = 0;

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

            ++cnt[x[y[i]]];

        for (i = 1; i < m; ++i)

            cnt[i] += cnt[i - 1];

        for (i = n - 1; i >= 0; --i)

            sa[--cnt[x[y[i]]]] = y[i];

        swap(x, y);

        x[sa[0]] = 0;

        p = 1;

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

            x[sa[i]] = cmp(y, sa[i - 1], sa[i], k) ? p - 1 : p++;

        m = p;

        if (p >= n)

            break;

    }

}

void gethgt(int n)

{

    int i, k = 0;

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

        ran[sa[i]] = i;

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

    {

        if (k)

            --k;

        int j = sa[ran[i] - 1];

        while (s[j + k] == s[i + k])

            ++k;

        height[ran[i]] = k;

    }

}

namespace RMQ

{

    void init(int l, int r)

    {

        int i, j;

        for (i = l; i <= r; ++i)

            dp[i][0] = height[i];

        for (j = 1; l + (1 << j) - 1 <= r; ++j)

            for (i = l; i + (1 << j) - 1 <= r; ++i)

                dp[i][j] = min(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);

    }

    int query(int l, int r)

    {

        int len = r - l + 1;

        int k = 0;

        while (1 << (k + 1) <= len)

            ++k;

        return min(dp[l][k], dp[r - (1 << k) + 1][k]);

    }

    LL LCP(int rankl, int rankr)

    {

        if(rankl > rankr)

            swap(rankl, rankr);

        if (rankl == rankr)

            return (LL)len - sa[rankl];

        else

            return (LL)query(rankl + 1, rankr);

    }

}

int main(void)

{

    int T, k, i;

    scanf("%d", &T);

    while (T--)

    {

        scanf("%d", &k);

        scanf("%s", s);

        len = strlen(s);

        DA(len + 1, 'z' + 1);

        gethgt(len);

        RMQ::init(1, len);

        LL ans = 0;

        for (i = 1; i + k - 1 <= len; ++i)

        {

            ans += RMQ::LCP(i, i + k - 1);

            if (i - 1 >= 1)

                ans -= RMQ::LCP(i - 1, i + k - 1);

            if (i + k <= len)

                ans -= RMQ::LCP(i, i + k);

            if (i - 1 >= 1 && i + k <= len)

                ans += RMQ::LCP(i - 1, i + k);

        }

        printf("%I64d\n", ans);

    }

    return 0;

}