Limak has a string S, that consists of N lowercase English letters.
Limak then created a new string by repeating S exactly K times.
For example, for S = "abcb" and K = 2, he would get "abcbabcb".
Your task is to count the number of subsequences "ab" (not necessarily consecutive) in the new string.
In other words, find the number pairs of indices i < j, such that the i-th and j-th characters in the new string are 'a' and 'b' respectively.

-----Input-----
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains two integers N and K, denoting the length of the initial string S and the number of repetitions respectively.
The second line contains a string S.
Its length is exactly N, and each of its characters is a lowercase English letter.

-----Output-----
For each test case, output a single line containing one integer — the number of subsequences "ab" in the new string.
For the given constraints, it can be proved that the answer fits in the 64-bit signed type.

-----Constraints-----
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 105
- 1 ≤ N * K ≤ 109 (in other words, the new string has length up to 109)

-----Example-----
Input:
3
4 2
abcb
7 1
aayzbaa
12 80123123
abzbabzbazab

Output:
6
2
64197148392731290

-----Explanation-----
Test case 1. Limak repeated the string "abcb" 2 times, and so he got "abcbabcb". There are 6 occurrences of the subsequence "ab":
- ABcbabcb (the two letters marked uppercase)
- AbcBabcb
- AbcbaBcb
- AbcbabcB
- abcbABcb
- abcbAbcB
Test case 2. Since K = 1, the new string is equal to the given S ("aayzbaa"). There are 2 occurrences of the subsequence "ab" in this string: AayzBaa and aAyzBaa.

Difficulty: MEDIUM_HARD
Tags: String algorithms

Combinatorics

Data structures

Mathematics
Skill types: Data structures

Starter code:

Solutions:
import collections
t = int(input())
while t:
	t -= 1
	(n, k) = map(int, input().split())
	s = input()
	cnt_b = 0
	d = collections.defaultdict(int)
	for i in s:
		if i == 'a':
			d[cnt_b] += 1
		if i == 'b':
			cnt_b += 1
	x = sum(d.values()) * cnt_b
	y = 0
	for key in d.keys():
		y += key * d[key]
	print(x * (k * (k + 1) // 2) - y * k)


for _ in range(int(input())):
	(a, b) = [int(c) for c in input().split()]
	s = str(input())
	k = 0
	p = 0
	z = 0
	for i in range(a):
		if s[i] == 'a':
			k += 1
		elif s[i] == 'b':
			p += 1
			z += k
	z = z * b + k * p * (b * (b - 1) // 2)
	print(z)


t = input()
for i in range(int(t)):
	x = list(map(int, input().split()))
	lngth = x[0]
	k = x[1]
	singlesum = 0
	multisum = 0
	count_a = 0
	count_b = 0
	seq = list(input())
	for i in range(lngth):
		if seq[i] == 'a':
			count_a += 1
		if seq[i] == 'b':
			singlesum += count_a
			count_b += 1
	multisum = (k - 1) * k * count_a * count_b // 2
	singlesum = singlesum * k
	print(singlesum + multisum)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	L = list(input())
	a = L.count('a')
	b = L.count('b')
	A = [0] * a
	i = 0
	j = 0
	countb = 0
	while i < a:
		if L[j] == 'a':
			A[i] = b - countb
			i += 1
		elif L[j] == 'b':
			countb += 1
		j += 1
	s = sum(A)
	ans = k * s
	ans += k * (k - 1) // 2 * b * a
	print(ans)


tulu = int(input())
for _ in range(tulu):
	(n, k) = [int(x) for x in input().split()]
	data = input()
	counterA = 0
	counterB = 0
	sumOfOneData = 0
	indexListOfB = []
	for i in range(n):
		if data[i] == 'a':
			counterA += 1
		if data[i] == 'b':
			counterB += 1
			sumOfOneData += counterA
	lulu = k * (k - 1) // 2
	result = lulu * counterB * counterA + k * sumOfOneData
	print(result)


def find():
	(n, k) = list(map(int, input().split()))
	s = list(input())
	lim = 0
	for i in range(n):
		if s[i] == 'a':
			lim = i
			break
	noa = 0
	sum = 0
	nob = 0
	maxb = 0
	i = len(s) - 1
	j = max(lim, 0)
	while i >= j:
		if s[i] == 'b':
			while i >= j and s[i] == 'b':
				nob += 1
				i -= 1
		elif s[i] == 'a':
			while i >= j and s[i] == 'a':
				noa += 1
				sum += nob
				i -= 1
		else:
			i -= 1
	maxb = nob
	while i >= 0:
		if s[i] == 'b':
			maxb += 1
		i -= 1
	print(sum * k + noa * (k * maxb * (k - 1)) // 2)
t = int(input())
for i in range(t):
	find()


def solve():
	(n, k) = map(int, input().split())
	string = input()
	c_a = c_b = ab = 0
	for i in string:
		if i == 'a':
			c_a += 1
		elif i == 'b':
			c_b += 1
			ab += c_a
	res = ab * k
	res += k * (k - 1) * c_a * c_b // 2
	print(res)
for _ in range(int(input())):
	solve()


t = int(input())
while t > 0:
	t = t - 1
	(n, k) = map(int, input().split())
	s = input()
	ca = 0
	cb = 0
	ans = 0
	for i in s:
		if i == 'a':
			ca += 1
		if i == 'b':
			ans += ca
			cb += 1
	print(ca * cb * k * (k - 1) // 2 + k * ans)


try:
	t = int(input())
	for i in range(t):
		(n, k) = map(int, input().split())
		s = input()
		l = [-1] * len(s)
		numb = s.count('b')
		x = numb
		for j in range(len(s)):
			if s[j] == 'a':
				l[j] = numb
			if s[j] == 'b':
				numb = numb - 1
		count1 = 0
		for j in range(len(l)):
			if l[j] > 0:
				count1 = count1 + k * (2 * l[j] + (k - 1) * x) // 2
			elif l[j] == 0:
				count1 = count1 + k * (2 * 0 + (k - 1) * x) // 2
		print(count1)
except:
	pass


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	t = 0
	(a, b) = (0, 0)
	for i in range(len(s) - 1, -1, -1):
		if s[i] == 'b':
			a += 1
		elif s[i] == 'a':
			b += a
	t = s.count('a') * s.count('b') * k * (k - 1) // 2
	print(b * k + t)


T = int(input())
for ix in range(T):
	(N, K) = input().split()
	(N, K) = (int(N), int(K))
	s = [input()]
	s = ''.join(s)
	bctr = [0] * N
	rlist = []
	res = 0
	if s[N - 1] == 'a':
		rlist.append(0)
	elif s[N - 1] == 'b':
		bctr[N - 1] = 1
	for i in range(N - 2, -1, -1):
		if s[i] == 'b':
			bctr[i] = bctr[i + 1] + 1
		else:
			bctr[i] = bctr[i + 1]
		if s[i] == 'a':
			rlist.append(bctr[i] + 0)
	rsum = sum(rlist)
	res = rsum * K
	res += bctr[0] * len(rlist) * ((K - 1) * K // 2)
	print(res)


try:
	for _ in range(int(input())):
		(n, k) = map(int, input().split())
		string = input()
		cnta = cntb = ab = 0
		for i in string:
			if i == 'a':
				cnta += 1
			elif i == 'b':
				cntb += 1
				ab += cnta
		final = ab * k
		final += k * (k - 1) * cnta * cntb // 2
		print(final)
except:
	pass


t = int(input())
for i in range(t):
	a = input()
	(n, k) = (int(a.split()[0]), int(a.split()[1]))
	s = input()
	l = list(s)
	ac = l.count('a')
	bc = l.count('b')
	u = 0
	co = ac * bc * k * (k - 1) // 2
	for i in range(n):
		if l[i] == 'a':
			u = u + bc
		elif l[i] == 'b':
			bc = bc - 1
	co = co + u * k
	print(co)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	s = input()
	na = s.count('a')
	nb = s.count('b')
	temp = nb
	summ = 0
	for i in range(len(s)):
		if s[i] == 'a':
			summ += nb
		elif s[i] == 'b':
			nb -= 1
		else:
			pass
	ans = summ * k + k * (k - 1) // 2 * na * temp
	print(ans)


T = int(input())
for _ in range(T):
	(N, K) = map(int, input().split())
	word = input()
	b_count = 0
	a_count = 0
	left_count = 0
	right_count = 0
	b_count = word.count('b')
	curr_b = 0
	for x in range(N):
		if word[x] == 'b':
			curr_b += 1
		elif word[x] == 'a':
			left_count += curr_b
			right_count += b_count - curr_b
	res = K * (K + 1)
	res = res // 2
	res = res * (left_count + right_count)
	res -= K * left_count
	print(res)


t = int(input())
for _ in range(t):
	(n, k) = [int(x) for x in input().split()]
	s = input()
	countA = 0
	countB = 0
	ans = 0
	for x in s:
		if x == 'a':
			countA += 1
		elif x == 'b':
			countB += 1
			ans += countA
	ans = ans * k + countB * countA * (k * (k - 1) // 2)
	print(ans)


t = int(input())
for i in range(t):
	(n, k) = list(map(int, input().strip().split()))
	s = input()
	A = s.count('a')
	B = s.count('b')
	b = 'ab'
	dp = [[0 for i in range(3)] for i in range(n + 1)]
	for i in range(3):
		dp[0][i] = 0
	for i in range(n + 1):
		dp[i][0] = 1
	for i in range(1, n + 1):
		for j in range(1, 3):
			if s[i - 1] == b[j - 1]:
				dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
			else:
				dp[i][j] = dp[i - 1][j]
	AB = dp[n][2]
	print(AB * k + A * B * k * (k - 1) // 2)


tulu = int(input())
for _ in range(tulu):
	(n, k) = [int(x) for x in input().split()]
	data = input()
	counterA = 0
	counterB = 0
	indexListOfA = []
	indexListOfB = []
	for i in range(n):
		if data[i] == 'a':
			counterA += 1
			indexListOfA.append(i)
		if data[i] == 'b':
			counterB += 1
			indexListOfB.append(i)
	sumOfOneData = 0
	for j in indexListOfA:
		lenB = len(indexListOfB)
		if lenB == 0:
			break
		flag = False
		while len(indexListOfB) > 0 and flag == False:
			if j < indexListOfB[0]:
				sumOfOneData += len(indexListOfB)
				flag = True
			else:
				indexListOfB.pop(0)
	lulu = k * (k - 1) // 2
	result = lulu * counterB * counterA + k * sumOfOneData
	print(result)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = list(input())
	s.append('b')
	ab = []
	c = 0
	su = 0
	d = 0
	ar = []
	for i in range(len(s)):
		if s[i] == 'a':
			c += 1
			d += 1
		elif s[i] == 'b':
			su += c
			ab.append(c)
			if d > 0:
				ar.append(d)
			ar.append(0)
			d = 0
	ab.pop()
	ar.pop()
	q = sum(ar)
	w = sum(ab)
	p = (k - 1) * k // 2
	ans = len(ab) * p * q + k * w
	print(ans)


t = int(input())
for I in range(t):
	(n, k) = map(int, input().split(' '))
	s = input()
	cnt_a = 0
	cnt_b = 0
	C = 0
	ans = 0
	for i in range(len(s)):
		if s[i] == 'a':
			cnt_a += 1
		elif s[i] == 'b':
			cnt_b += 1
			C += cnt_a
	ans += C * k
	ans += k * (k - 1) // 2 * cnt_a * cnt_b
	print(ans)


for _ in range(int(input())):
	[n, r] = [int(i) for i in input().split()]
	a = input()
	b = []
	c = 0
	for i in a:
		if i == 'a':
			c += 1
		if i == 'b':
			b.append(c)
	d = 0
	for i in b:
		d += i * r + r * (r - 1) * c // 2
	print(d)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	if 'a' not in s:
		print(0)
		continue
	cnta = 0
	cntb = 0
	c = 0
	for i in s:
		if i == 'a':
			cnta += 1
		elif i == 'b':
			cntb += 1
			c += cnta
	ans = c * k
	ans = ans + k * (k - 1) // 2 * cnta * cntb
	print(ans)


def summer(n, d, a):
	return n * (2 * a + (n - 1) * d) // 2
t = int(input())
while t:
	t -= 1
	(x, y) = input().split()
	(x, y) = (int(x), int(y))
	a = input()
	ans = i = count = 0
	countb = a.count('b')
	while i < x:
		if a[i] == 'a':
			ans += summer(y, countb, countb - count)
		elif a[i] == 'b':
			count += 1
		i += 1
	print(ans)


t = int(input())
for i in range(t):
	(l, n) = map(int, input().split())
	s = input()
	count_a = s.count('a')
	count_b = s.count('b')
	count = a = b = 0
	for i in s:
		if i == 'a':
			a += 1
		elif i == 'b':
			count += a
	a = count
	d = count_a * count_b
	ans = n * (2 * a + (n - 1) * d) // 2
	print(ans)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	string = input()
	a = 0
	b = 0
	ab = 0
	for index in range(n):
		if string[index] == 'a':
			a += 1
		elif string[index] == 'b':
			b += 1
			ab += a
	difference = a * b
	startTerm = ab
	endTerm = startTerm + (k - 1) * difference
	print(k * (startTerm + endTerm) // 2)


for u in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	d = 0
	c = 0
	x = s.count('b')
	for i in range(n):
		if s[i] == 'b':
			c += 1
		elif s[i] == 'a':
			d += k * (k + 1) // 2 * x - k * c
	print(d)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	ac = 0
	bc = 0
	t = 0
	for i in range(n):
		if s[i] == 'a':
			ac += 1
		if s[i] == 'b':
			bc += 1
			t += ac
	r = k * t
	r += k * (k - 1) // 2 * ac * bc
	print(r)


t = int(input())
for x in range(t):
	(n, k) = input().split()
	(n, k) = (int(n), int(k))
	str = input()
	i = 0
	count1 = 0
	total = 0
	i = 0
	while i < n:
		if str[i] == 'a':
			count1 = count1 + 1
		i = i + 1
	(count2, count3) = (0, 0)
	i = 0
	while i < n:
		if str[i] == 'a':
			count2 = count2 + 1
		elif str[i] == 'b':
			total = total + (k * count2 + k * (k - 1) * count1 // 2)
		i = i + 1
	print(total)


T = int(input())
while T != 0:
	T = T - 1
	(N, K) = map(int, input().split())
	S = input()
	S1 = S + S
	sub = 'ab'
	lookup = [[0] * (2 * N + 1) for _ in range(3)]
	for i in range(0, 2 * N + 1):
		lookup[0][i] = 1
	for i in range(1, 2 * N + 1):
		for j in range(1, 3):
			if S1[i - 1] == sub[j - 1]:
				lookup[j][i] = lookup[j - 1][i - 1] + lookup[j][i - 1]
			else:
				lookup[j][i] = lookup[j][i - 1]
	base = lookup[2][N]
	inc = lookup[2][2 * N] - 2 * base
	ans = K * base + (K - 1) * K * inc // 2
	print(ans)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	string = input()
	counta = 0
	countb = 0
	countab = 0
	for index in range(n):
		if string[index] == 'a':
			counta += 1
		elif string[index] == 'b':
			countb += 1
			countab += counta
	difference = counta * countb
	startTerm = countab
	endTerm = startTerm + (k - 1) * difference
	print(k * (startTerm + endTerm) // 2)


t = int(input())
(s, arr) = ('', [])
for i in range(0, t):
	(su, cnta, cntb) = (0, 0, 0)
	arr = [int(m) for m in input().split(' ')]
	s = input()
	for j in range(arr[0]):
		if s[j] == 'a':
			cnta += 1
		elif s[j] == 'b':
			su += cnta
			cntb += 1
	su = su * arr[1] + cntb * cnta * (arr[1] * (arr[1] - 1) // 2)
	print(su)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	ans = 0
	total = 0
	b = 0
	s = input()
	for i in range(n):
		if s[i] == 'a':
			ans += 1
		if s[i] == 'b':
			total += ans
			b += 1
	x = b * ans
	sum = 2 * total + (k - 1) * x
	sum = sum * k // 2
	print(sum)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	l = [-1] * len(s)
	numb = s.count('b')
	x = numb
	for j in range(len(s)):
		if s[j] == 'a':
			l[j] = numb
		if s[j] == 'b':
			numb = numb - 1
	count1 = 0
	for j in range(len(l)):
		if l[j] > 0:
			count1 = count1 + k * (2 * l[j] + (k - 1) * x) // 2
		elif l[j] == 0:
			count1 = count1 + k * (2 * 0 + (k - 1) * x) // 2
	print(count1)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = [x for x in input().strip()]
	c1 = s.count('a')
	c2 = s.count('b')
	ans = 0
	m = 0
	for x in s:
		if x == 'b':
			m += 1
		if x == 'a':
			ans += k * (k + 1) // 2 * c2 - k * m
	print(ans)


t = int(input())
for _1 in range(t):
	(n, k) = map(int, input().split())
	s = input().strip()
	(a, b, ab) = (0, 0, 0)
	for x in range(len(s)):
		if s[x] == 'a':
			a += 1
		if s[x] == 'b':
			b += 1
			ab += a
	print(ab * k + a * b * ((k - 1) * k) // 2)


t = int(input())
while t:
	(l, k) = map(int, input().split())
	s = input()
	count = 0
	acount = 0
	for i in s:
		if i == 'a':
			acount += 1
		if i == 'b':
			count += acount
	count *= k
	count += s.count('a') * s.count('b') * k * (k - 1) // 2
	print(count)
	t -= 1


T = int(input())
for t in range(T):
	(n, k) = map(int, input().split(' '))
	s = input()
	f = 0
	ct = 0
	nob = [0 for i in range(n)]
	if s[n - 1] == 'b':
		nob[n - 1] = 1
	for i in range(n - 2, -1, -1):
		if s[i] == 'b':
			nob[i] = nob[i + 1] + 1
		else:
			nob[i] = nob[i + 1]
	res = 0
	noba = []
	for i in range(n):
		if s[i] == 'a':
			noba.append(nob[i])
	ptr = 0
	ct = 0
	for ptr in range(len(noba)):
		res += noba[ptr]
	res *= k
	res += s.count('a') * nob[0] * k * (k - 1) // 2
	print(res)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	a = s.count('a')
	b = s.count('b')
	cur = b * k * (k + 1) // 2
	ans = 0
	for i in s:
		if i == 'a':
			ans += cur
		elif i == 'b':
			cur -= k
	print(ans)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	s = input()
	c1 = 0
	c2 = 0
	c3 = 0
	for j in range(n):
		if s[j] == 'a':
			c1 += 1
		elif s[j] == 'b':
			c2 += 1
			c3 += c1
	d = c1 * c2
	x = c3
	ans = x + (k - 1) * d
	print(k * (x + ans) // 2)


def get_ans(n, k, s):
	totalB = s.count('b')
	initialB = totalB * k
	ans = 0
	for i in s:
		if i == 'b':
			initialB -= 1
		elif i == 'a':
			APa = initialB
			APd = -totalB
			APn = k
			ans += APn * (2 * APa + (APn - 1) * APd) // 2
	return ans
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	print(get_ans(n, k, s))


from functools import reduce
T = int(input())
for i in range(T):
	count = 0
	a = 0
	b = 0
	Count = 0
	(N, K) = map(int, input().split())
	S = str(input().lower())
	for j in S:
		if j == 'a':
			a += 1
		elif j == 'b':
			b += 1
			count += a
	Count = K * (K - 1) * a * b // 2
	Count = Count + K * count
	print(Count)


for t in range(int(input())):
	(N, K) = [int(i) for i in input().strip().split()]
	s = input()
	ans = 0
	n_b_s = s.count('b')
	b_f = 0
	for i in range(len(s)):
		if s[i] == 'b':
			b_f += 1
			continue
		if s[i] == 'a':
			ans += K * (K + 1) // 2 * n_b_s - b_f * K
	print(ans)


T = int(input())
for i in range(T):
	(N, K) = map(int, input().split())
	S = input()
	(aCount, bCount, abCount) = (0, 0, 0)
	for x in S:
		if x == 'a':
			aCount += 1
		elif x == 'b':
			bCount += 1
			abCount += aCount
	abCount = abCount * K + bCount * aCount * (K * (K - 1) // 2)
	print(abCount)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	l = [str(i) for i in input()]
	ac = l.count('a')
	bc = l.count('b')
	u = 0
	co = ac * bc * k * (k - 1) // 2
	for i in range(n):
		if l[i] == 'a':
			u = u + bc
		elif l[i] == 'b':
			bc = bc - 1
	co = co + u * k
	print(co)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	(aCount, bCount, abCount) = (0, 0, 0)
	for x in s:
		if x == 'a':
			aCount += 1
		elif x == 'b':
			bCount += 1
			abCount += aCount
	abCount = abCount * k + bCount * aCount * (k * (k - 1) // 2)
	print(abCount)


def binarySearch(arr, l, r, x):
	if r >= l:
		mid = l + (r - l) // 2
		if arr[mid] == x:
			return mid
		elif arr[mid] > x:
			return binarySearch(arr, l, mid - 1, x)
		else:
			return binarySearch(arr, mid + 1, r, x)
	elif l < len(arr):
		return l
	else:
		return -1
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	posn = []
	for i in range(len(s)):
		if s[i] == 'b':
			posn.append(i)
	tot = 0
	for i in range(n):
		if posn == []:
			break
		elif s[i] == 'a':
			z = binarySearch(posn, 0, len(posn) - 1, i)
			if z != -1 and posn[z] < len(s):
				if s[posn[z]] == 'b':
					z += 1
					tot += len(posn) - z + 1
	tot *= k
	k1 = s.count('a')
	k2 = s.count('b')
	tot += k1 * k2 * (k - 1) * k // 2
	print(tot)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	st = input()
	a = st.count('a')
	b = st.count('b')
	c = 0
	ca = 0
	for i in range(n):
		if st[i] == 'a':
			ca += 1
		if st[i] == 'b':
			c += ca
	print(a * b * (k * (k - 1) // 2) + c * k)


T = int(input())
for t in range(0, T):
	D = [int(x) for x in input().split(' ')]
	S = list(input())
	na = 0
	nb = 0
	ng = 0
	for i in range(len(S) - 1, -1, -1):
		if S[i] == 'b':
			nb += 1
		elif S[i] == 'a':
			na += nb
			ng += 1
	sm = D[1] * (D[1] - 1) // 2 * ng * nb + D[1] * na
	print(sm)


for i in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	s = input()
	a = 0
	b = 0
	ahere = 0
	for i in s:
		if i == 'a':
			a += 1
		elif i == 'b':
			b += 1
			ahere += a
	print(ahere * k + (k - 1) * k // 2 * a * b)


def num_subsequences(seq, sub):
	(m, n) = (len(seq), len(sub))
	table = [0] * n
	for i in range(m):
		previous = 1
		for j in range(n):
			current = table[j]
			if seq[i] == sub[j]:
				table[j] += previous
			previous = current
	return table[n - 1] if n else 1
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	x = int(num_subsequences(s, 'ab'))
	q = s.rfind('b')
	na = 0
	for ch in s:
		if ch == 'a':
			na += 1
	nb = 0
	for ch in s:
		if ch == 'b':
			nb += 1
	po = na * nb
	y = int(po * (k * (k - 1)) // 2)
	print(k * x + y)


import io
import sys

def test_data():
	return io.StringIO('3\n4 2\nabcb\n7 1\naayzbaa\n12 80123123\nabzbabzbazab')

def get_input(source):
	with source as lines:
		t = int(next(lines))
		for _ in range(t):
			(n, k) = list(map(int, next(lines).strip().split(' ')))
			s = next(lines).strip()
			yield (s, k)

def calc(s, k):
	diff = []
	cur = 0
	num_b = 0
	for c in s:
		if c == 'b':
			cur += 1
			num_b += 1
		diff.append(cur)
	if num_b == 0:
		return 0
	tri = k * (k + 1) // 2
	tri_b = num_b * tri
	tot = 0
	for i in range(len(s)):
		if s[i] == 'a':
			tot += tri_b - diff[i] * k
	return tot
inp = test_data() if '-test' in sys.argv else sys.stdin
for args in get_input(inp):
	print(calc(*args))


t = int(input())
while t:
	t -= 1
	lengrep = [int(x) for x in input().strip().split()]
	leng = lengrep[0]
	rep = lengrep[1]
	B_cnt_tNow = 0
	s = input().strip()
	i = leng - 1
	B_cnt_total = 0
	A_cnt_total = 0
	while i >= 0:
		if s[i] == 'b':
			B_cnt_tNow += 1
		elif s[i] == 'a':
			A_cnt_total += 1
			B_cnt_total += B_cnt_tNow
		i -= 1
	count = rep * B_cnt_total
	tem = rep * (rep - 1)
	tem = tem // 2
	count = count + A_cnt_total * B_cnt_tNow * tem
	print(count)


def ti():
	return tuple(map(int, input().split()))

def li():
	return list(map(int, input().split()))

def si():
	return input().split()

def ii():
	return int(input())

def ip():
	return input()
for tastcas in range(int(input())):
	(n, k) = li()
	s = ip()
	a = b = x = 0
	for i in range(n):
		if s[i] == 'a':
			a += 1
		elif s[i] == 'b':
			b += 1
			x += a
	print(x * k + k * (k - 1) // 2 * a * b)


tt = int(input())
for _ in range(tt):
	(n, k) = map(int, input().split(' '))
	s = input()
	c1 = 0
	ca = 0
	cb = 0
	for c in s:
		if c == 'a':
			ca += 1
		elif c == 'b':
			cb += 1
			c1 += ca
	x = k * (k - 1) // 2
	res = c1 * k + x * ca * cb
	print(res)


for t in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	a = 0
	b = 0
	ab = 0
	for i in range(n):
		if s[i] == 'a':
			a += 1
		elif s[i] == 'b':
			b += 1
	aa = a
	bb = b
	for i in range(n):
		if s[i] == 'a':
			ab += bb
		elif s[i] == 'b':
			bb -= 1
	print(k * ab + a * b * ((k - 1) * k) // 2)


for t in range(int(input())):
	temp = list(map(int, input().split()))
	n = temp[0]
	k = temp[1]
	s = input()
	front = []
	back = []
	for i in range(n):
		front.append(0)
		back.append(0)
	for i in range(1, n):
		if s[i - 1] == 'b':
			back[i] = back[i - 1] + 1
		else:
			back[i] = back[i - 1]
	i = n - 2
	while i >= 0:
		if s[i + 1] == 'b':
			front[i] = front[i + 1] + 1
		else:
			front[i] = front[i + 1]
		i -= 1
	fs = 0
	bs = 0
	for i in range(n):
		if s[i] == 'a':
			fs += front[i]
			bs += back[i]
	v1 = fs * k * (k + 1) // 2
	v2 = bs * k * (k - 1) // 2
	print(v1 + v2)


t = int(input())
while t > 0:
	(n, k) = list(map(int, input().split(' ')))
	s = input()
	countsOfB = [0] * len(s)
	if s[len(s) - 1] == 'b':
		countsOfB[len(s) - 1] = 1
	for index in range(len(s) - 2, -1, -1):
		countsOfB[index] = countsOfB[index + 1]
		if s[index] == 'b':
			countsOfB[index] += 1
	totalBinString = countsOfB[0]
	totalAinString = 0
	for eachChar in s:
		if eachChar == 'a':
			totalAinString += 1
	totalPairs = 0
	for index in range(0, len(s)):
		if s[index] == 'a':
			totalPairs = totalPairs + countsOfB[index] * k
	extra = k * (k - 1) // 2 * totalBinString * totalAinString
	print(totalPairs + extra)
	t -= 1


for _ in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	s = input()
	temp_a = y = 0
	a = s.count('a')
	for i in s:
		if i == 'a':
			temp_a += 1
		elif i == 'b':
			x = temp_a
			y += k * x + k * (k - 1) // 2 * a
	print(y)