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: interview

Starter code:

Solutions:
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
        #print(l)
        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


# cook your dish here
# cook your dish here
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)


# cook your dish here
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 _ 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)

# cook your dish here
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)


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             #for each b considers all a 
        
        final=ab*k 
        final+=k*(k-1)*cnta*cntb//2 
        
        print(final)
        
except:
    pass


#Coded By Ujjwal Bharti
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)

#Coded By Ujjwal Bharti
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)

# import sys
# sys.stdin=open('input.txt','r')
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 _ 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)
            # print(x, left_count, right_count)
    res = K*(K+1)
    res = res//2
    res = res*(left_count+right_count)
    res-=K*left_count
    print(res)

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())
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)


# 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
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)

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))


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)    

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)

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
    #print(na,nb)
    summ = 0
    for i in range(len(s)):
        if(s[i]=='a'):
            summ += nb
        elif(s[i]=='b'):
            nb -=1
        else:
            pass
    #print(summ)
    ans = summ*k + ((k*(k-1))//2)*na*temp
    print(ans)


# cook your dish here
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)

    else:
        if 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)
    # print(posn)
    tot = 0
    for i in range(n):
        if posn == []:
            break
        else:
            if s[i] == 'a':
                z = binarySearch(posn,0,len(posn)-1,i)

                if z!=-1 and posn[z]<len(s):

                    # print(posn[z])
                    if s[posn[z]] == 'b':
                        z+=1
                        tot+=len(posn)-z+1
    tot*=k
    k1 = s.count('a')
    k2 = s.count('b')
    # k1*=(k-1)
    tot+=((k1*k2)*(k-1)*k)//2
    print(tot)





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)

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 _ 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)