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.
# cook your dish here
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
	#print(lookup)
	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]
	#print(lookup)
	base = lookup[2][N]
	#print('base='+str(base))
	inc = lookup[2][2*N] - 2*base
	#print('inc='+str(inc))
	ans = K*base + ((K-1)*(K)*inc)//2
	print(ans)
	
# cook your dish here
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
	#print(lookup)
	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]
	#print(lookup)
	base = lookup[2][N]
	#print('base='+str(base))
	inc = lookup[2][2*N] - 2*base
	#print('inc='+str(inc))
	ans = K*base + ((K-1)*(K)*inc)//2
	print(ans)
	