If there's pairs of nearby places where $$$T$$$ matches $$$(i - p,i)$$$ and $$$(i,i + q)$$$ that $$$p \neq q$$$,we found that:

• $$$p$$$ is the length of a border
• $$$q$$$ is the length of an another border
• The shorter border is a border of a larger border.

Then we will found that if $$$p \gt q$$$, thenwe found pair $$$(i - q,i)$$$ exists,or $$$(i,i + p)$$$ exists while $$$p \lt q$$$, which are not valid when we deem pairs $$$(i - p,i)$$$,$$$(i,i + q)$$$ as nearby place that match,so $$$p = q$$$ garenteed.

if there's border $$$i + p,i,i - q$$$ as no border length $$$l$$$ that $$$i - q \lt l \lt i$$$ or $$$i \lt l \lt i + p$$$,we'll found:

• $$$p,q$$$ are the lengths of borders.
• $$$i - p$$$ is the length of a border of the border with length $$$i$$$.
• $$$i$$$ is the length of a border of the border with length $$$i + q$$$.

We will find $$$i - q \lt i - p \lt i$$$ or $$$i \lt i + q \lt i + p$$$, making it incorrect,so $$$p = q$$$

In fact,if there's a way for an addition $$$x$$$,we can form a graph of $$$x$$$ nodes and deem other additions as edges to form a graph. We'll have to run a shortest paths algorithm to get the smallest lengths with garenteed modules.

But the naive algorithm is too slow,as borders form $$$\operatorname{O}(\log |S|)$$$ distinct arthmetic sequences,we just start updating with an arthmetic sequence for $$$\operatorname{O}(\log |S|)$$$ rounds. Every time we start with the smallest node in each cycle and can update all the nodes in the cycle using a monotonous queue(as a sliding window problem) in $$$\operatorname{O}(x)$$$.

At first we start with a graph with $$$|S|$$$ nodes and only node $$$0$$$ with a distance $$$|S|$$$, Then we may change $$$x$$$ to $$$x'$$$,it's also easy to start form the node with smallest distance in each cycle and update it in $$$\operatorname{O}(x + x')$$$.

At last we get an $$$\operatorname{O}(|S|\log |S|)$$$ algorithm.

#include<bits/stdc++.h>
using namespace std;
int t,n,bor[500009],diff[500009],dt[500009],shlink[500009],q[500009],head,tail;
long long w,dp1[500009],dp2[500009];
int mx[500009];
const long long INF = 1998244353999911659ll;
char c[500009];
int gcd(int x,int y){
	return y == 0 ? x : gcd(y,x % y);
}
int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d %lld",&n,&w);
		scanf(" %s",c + 1);
		bor[1] = 0;
		for(int i = 2; i <= n; i ++){
			int t = bor[i - 1];
			while(t != 0 && c[i] != c[t + 1])
				t = bor[t];
			if(c[i] == c[t + 1])
				t ++;
			bor[i] = t;
		}
		for(int i = 1; i <= n; i ++){
			diff[i] = i - bor[i];
			shlink[i] = bor[i];
			if(diff[i] == diff[bor[i]])
				shlink[i] = shlink[bor[i]];
		}
		//for(int i = n; i > 0; i = bor[i])
		//	printf("%d\n",bor[i]);
		//puts("OK");
		dp1[0] = n;
		for(int i = 1; i < n; i ++){
			dp1[i] = INF;
		}
		int lst = n;
		for(int i = bor[n]; i != 0; i = shlink[i]){
			int nw = n - i;
			int ls = (i - shlink[i]) / diff[i] - 1;
			for(int j = 0; j < nw; j ++){
				dp2[j] = INF;
			}
			int fp = gcd(n - i,lst);
			for(int j = 0; j < fp; j ++){
				mx[j] = n + 1;
				dp2[n + 1] = INF;
			}
			for(int j = 0; j < lst; j ++){
				dp2[dp1[j] % nw] = min(dp2[dp1[j] % nw],dp1[j]);
				if(dp2[mx[dp1[j] % fp]] > dp2[dp1[j] % nw])
					mx[dp1[j] % fp] = dp1[j] % nw;
			}
			
			for(int j = 0; j < fp; j ++){
				long long mn = dp2[mx[j]];
				if(mx[j] == n + 1)
					continue;
				for(int k = (mx[j] + lst) % nw; k != mx[j]; k = (k + lst) % nw){
					dt[k] = -1;
					mn = min(mn + lst,dp2[k]);
					dp2[k] = mn;
				}
			}
		//	printf("%d\n",i);
			fp = gcd(nw,diff[i]);
			for(int j = 0; j < fp; j ++){
				mx[j] = n + 1;
			}
				dp1[n + 1] = INF;
			for(int j = 0; j < nw; j ++){
				dt[j] = 0;
				dp1[j] = dp2[j];
				if(dp1[j] < dp1[mx[j % fp]])
					mx[j % fp] = j;
			}
			for(int j = 0; j < fp; j ++){
				head = 1,tail = 0;
				for(int k = mx[j],l = 0; l < nw / fp; l ++,k = (k + diff[i]) % nw){
					dt[k] = l;
					while(head <= tail && l - dt[q[head]] > ls)
						head ++;
					if(head <= tail)
						dp1[k] = min(dp1[k],dp1[q[head]] + 1ll * l * diff[i] - 1ll * dt[q[head]] * diff[i] + nw);
					while(head <= tail && dp1[k] - 1ll * l * diff[i] <= dp1[q[tail]] - 1ll * dt[q[tail]] * diff[i])
						tail --;
					q[++tail] = k;
					//printf("%d %lld\n",k,dp1[k]);
				}
			}
			lst = nw;
		}
		long long ans = 0;
		for(int i = 0; i < lst; i ++){
			//printf("%d %lld\n",i,dp1[i]);
			if(dp1[i] <= w)
				ans = ans + (w - dp1[i]) / lst + 1;
		}
		printf("%lld\n",ans);
	}
}