1 #include <cstdio>
  2 #include <iostream>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <set>
  6 #include <map>
  7 #include <string>
  8 #include <cstring>
  9 #include <stack>
 10 #include <queue>
 11 #include <cmath>
 12 #include <ctime>
 13 #include <bitset>
 14 #include <utility>
 15 #include <assert.h>
 16 using namespace std;
 17 #define rank rankk
 18 #define mp make_pair
 19 #define pb push_back
 20 #define xo(a,b) ((b)&1?(a):0)
 21 #define tm tmp
 22 //#define LL ll
 23 typedef unsigned long long ull;
 24 typedef pair<int,int> pii;
 25 typedef long long ll;
 26 typedef pair<ll,int> pli;
 27 typedef pair<ll,ll> pll;
 28 const int INF=0x3f3f3f3f;
 29 const ll INFF=0x3f3f3f3f3f3f3f3fll;
 30 const int MAX=1e5+5;
 31 //const ll MAXN=2e8;
 32 const int MAX_N=MAX;
 33 const ll MOD=998244353;
 34 //const long double pi=acos(-1.0);
 35 //const double eps=0.00000001;
 36 int gcd(int a,int b){return b?gcd(b,a%b):a;}
 37 template<typename T>inline T abs(T a) {return a>0?a:-a;}
 38 template<class T> inline
 39 void read(T& num) {
 40     bool start=false,neg=false;
 41     char c;
 42     num=0;
 43     while((c=getchar())!=EOF) {
 44         if(c==‘-‘) start=neg=true;
 45         else if(c>=‘0‘ && c<=‘9‘) {
 46             start=true;
 47             num=num*10+c-‘0‘;
 48         } else if(start) break;
 49     }
 50     if(neg) num=-num;
 51 }
 52 inline ll powMM(ll a,ll b,ll M){
 53     ll ret=1;
 54     a%=M;
 55 //    b%=M;
 56     while (b){
 57         if (b&1) ret=ret*a%M;
 58         b>>=1;
 59         a=a*a%M;
 60     }
 61     return ret;
 62 }
 63 void open()
 64 {
 65 //    freopen("1009.in","r",stdin);
 66     freopen("out.txt","w",stdout);
 67 }
 68 const int MAXN=100005;
 69 int t1[MAXN],t2[MAXN],c[MAXN];//求SA数组需要的中间变量，不需要赋值
 70 //待排序的字符串放在s数组中，从s[0]到s[n-1],长度为n,且最大值小于m,
 71 //除s[n-1]外的所有s[i]都大于0，r[n-1]=0
 72 //函数结束以后结果放在sa数组中
 73 bool cmp(int *r,int a,int b,int l)
 74 {
 75     return r[a] == r[b] && r[a+l] == r[b+l];
 76 }
 77 void da(int str[],int sa[],int rank[],int height[],int n,int m)
 78 {
 79     str[n++]=0;
 80     int i, j, p, *x = t1, *y = t2;
 81     //第一轮基数排序，如果s的最大值很大，可改为快速排序
 82     for(i = 0;i < m;i++)c[i] = 0;
 83     for(i = 0;i < n;i++)c[x[i] = str[i]]++;
 84     for(i = 1;i < m;i++)c[i] += c[i-1];
 85     for(i = n-1;i >= 0;i--)sa[--c[x[i]]] = i;
 86     for(j = 1;j <= n; j <<= 1)
 87     {
 88         p = 0;
 89         //直接利用sa数组排序第二关键字
 90         for(i = n-j; i < n; i++)y[p++] = i;//后面的j个数第二关键字为空的最小
 91         for(i = 0; i < n; i++)if(sa[i] >= j)y[p++] = sa[i] - j;
 92         //这样数组y保存的就是按照第二关键字排序的结果
 93         //基数排序第一关键字
 94         for(i = 0; i < m; i++)c[i] = 0;
 95         for(i = 0; i < n; i++)c[x[y[i]]]++;
 96         for(i = 1; i < m;i++)c[i] += c[i-1];
 97         for(i = n-1; i >= 0;i--)sa[--c[x[y[i]]]] = y[i];
 98         swap(x,y);
 99         //根据sa和x数组计算新的x数组 swap(x,y);
100         p = 1; x[sa[0]] = 0;
101         for(i = 1;i < n;i++)
102             x[sa[i]] = cmp(y,sa[i-1],sa[i],j)?p-1:p++;
103         if(p >= n)break;
104         m = p;//下次基数排序的最大值
105     }
106     int k = 0; n--;
107     for(i = 0;i <= n;i++)rank[sa[i]] = i;
108     for(i = 0;i < n;i++)
109     {
110         if(k)k--;
111         j = sa[rank[i]-1]; while(str[i+k] == str[j+k])k++; height[rank[i]] = k;
112     }
113 }
114 int rank[MAXN],height[MAXN];
115 int RMQ[MAXN];
116 int mm[MAXN];
117 int best[20][MAXN];
118 void initRMQ(int n)
119 {
120     mm[0]=-1;
121     for(int i=1;i<=n;i++)
122     mm[i]=((i&(i-1))==0)?mm[i-1]+1:mm[i-1];
123     for(int i=1;i<=n;i++)best[0][i]=i;
124     for(int i=1;i<=mm[n];i++)
125     for(int j=1;j+(1<<i)-1<=n;j++)
126     {
127         int a=best[i-1][j];
128         int b=best[i-1][j+(1<<(i-1))];
129         if(RMQ[a]<RMQ[b])best[i][j]=a; else best[i][j]=b;
130     }
131 }
132 int askRMQ(int a,int b)
133 {
134     int t; t=mm[b-a+1];
135     b-=(1<<t)-1;
136     a=best[t][a];b=best[t][b];
137     return RMQ[a]<RMQ[b]?a:b;
138 }
139 int lcp(int a,int b)
140 {
141     a=rank[a];b=rank[b];
142     if(a>b)swap(a,b);
143     return height[askRMQ(a+1,b)];
144 }
145 int t,k,len;
146 char sts[MAXN];
147 int st[MAXN],sa[MAXN];
148 multiset<int>s;
149 ll cal(int x)
150 {
151     ll an=0;
152     if(x==1)
153     {
154         an=1LL*len*(len+1LL)/2LL;
155         for(int i=1;i<=len;i++)an-=height[i];
156     }
157     else
158     {
159         s.clear();
160         for(int i=1;i<=x-1;i++)s.insert(height[i]);
161         for(int i=x;i<=len;i++)
162         {
163             int pre=*s.begin();s.erase(s.find(height[i-x+1]));s.insert(height[i]);
164             printf("%d %d!\n",pre,*s.begin());
165             an+=max(0,*s.begin()-pre);
166         }
167     }
168     return an;
169 }
170 int main()
171 {
172     scanf("%d",&t);
173     while(t--)
174     {
175         scanf("%d",&k);
176         scanf("%s",sts);len=strlen(sts);
177         memset(height,0,sizeof(height));
178         for(int i=0;i<len;i++)st[i]=sts[i]-‘a‘+1;
179         da(st,sa,rank,height,len,27);
180         for(int i=1;i<=len;i++)
181             printf("%d\n",height[i]);
182         printf("%lld\n",cal(k)-cal(k+1));
183     }
184 }