Read problems statements in Mandarin chinese, Russian and Vietnamese as well. 

You are given an integer $n$ and a string $s$ consisting only of characters 'a' and 'b'. Consider a string $t = \underbrace{s + s + \dots + s}_{n\text{ times}}$, i.e. the string obtained by concatenating $n$ copies of $s$.

Find the number of non-empty prefixes of $t$ in which the number of occurrences of 'a' is strictly greater than the number of occurrences of 'b'.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first and only line of each test case contains the string $s$ and the integer $n$, separated by a single space. 

------  Output ------
For each test case, print a single line containing one integer — the number of valid prefixes.

------  Constraints  ------
$1 ≤ T ≤ 100$
$1 ≤ |s| ≤ 10^{3}$
$1 ≤ n ≤ 10^{9}$
each character of $s$ is either 'a' or 'b'

------  Subtasks ------
Subtask #1 (30 points): $1 ≤ n ≤ 10^{3}$

Subtask #2 (70 points): original constraints

----- Sample Input 1 ------ 
3
aba 2
baa 3
bba 3
----- Sample Output 1 ------ 
5
6
0
----- explanation 1 ------ 
Example case 1: The string $t$ is "abaaba". It has five prefixes which contain more a-s than b-s: "a", "aba", "abaa", "abaab" and "abaaba".

Example case 2: The string $t$ is "baabaabaa". The strings "baa", "baaba", "baabaa", "baabaab", "baabaaba" and "baabaabaa" are the six valid prefixes.

Example case 3: The string $t$ is "bbabbabba". There is no prefix of this string which consists of more a-s than b-s. Therefore, the answer is zero.

Difficulty: MEDIUM_HARD
Tags: Mathematics

Starter code:

Solutions:
import sys

def main():
	for line in sys.stdin:
		f = int(line.strip())
		while f > 0:
			n = 0
			count1 = 0
			count2 = 0
			count = 0
			sum = 0
			flag = 0
			tempcount = 0
			(s, n) = input().split()
			n = int(n)
			for i in range(n):
				tempcount = 0
				for j in range(len(s)):
					if s[j] == 'a':
						count1 += 1
					elif s[j] == 'b':
						count2 += 1
					if count1 > count2:
						count += 1
						tempcount += 1
				if count1 == count2:
					flag = 1
					break
				if tempcount == len(s):
					flag = 2
					break
				if tempcount == 0:
					break
			if flag == 1:
				sum = count * n
			elif flag == 2:
				sum = count + (n - 1 - i) * len(s)
			else:
				sum = count
			print(sum)
			f -= 1
main()


t = int(input())
for i in range(t):
	e = input().split()
	s = e[0]
	n = int(e[1])
	c1 = 0
	c2 = 0
	f = 0
	for j in range(len(s)):
		if s[j] == 'a':
			c1 += 1
		else:
			c2 += 1
		if c1 > c2:
			f += 1
	if n == 1:
		print(f)
	else:
		a = ['rand', f]
		for j in range(2, 1050):
			for k in range(len(s)):
				if s[k] == 'a':
					c1 += 1
				else:
					c2 += 1
				if c1 > c2:
					f += 1
			a.append(f)
			if j == n:
				print(f)
				break
			if j - 2 >= 1 and a[j] - a[j - 1] == a[j - 1] - a[j - 2]:
				d = a[j] - a[j - 1]
				v = f + (n - j) * d
				print(v)
				break


t = input()
for _ in range(int(t)):
	temp = input().split()
	s = temp[0]
	n = int(temp[1])
	ca = 0
	cb = 0
	pref = 0
	for i in range(len(s)):
		if s[i] == 'a':
			ca += 1
		else:
			cb += 1
		if ca > cb:
			pref += 1
	if n == 1:
		print(pref)
	else:
		a = ['rand', pref]
		for i in range(2, 1050):
			for j in range(len(s)):
				if s[j] == 'a':
					ca += 1
				else:
					cb += 1
				if ca > cb:
					pref += 1
			a.append(pref)
			if i == n:
				print(pref)
				break
			if i - 2 >= 1 and a[i] - a[i - 1] == a[i - 1] - a[i - 2]:
				diff = a[i] - a[i - 1]
				val = pref + (n - i) * diff
				print(val)
				break


for i in range(int(input())):
	(string, n) = input().split(' ')
	n = int(n)
	a = 0
	b = 0
	count = 0
	for i in string:
		if i == 'a':
			a += 1
		else:
			b += 1
		if a > b:
			count += 1
	if a == b:
		print(count * n)
	if a > b:
		m = int(b / (a - b))
		m += 1
		a_1 = 0
		b_1 = 0
		count_1 = 0
		if n > m:
			for i in string * m:
				if i == 'a':
					a_1 += 1
				else:
					b_1 += 1
				if a_1 > b_1:
					count_1 += 1
			count_1 += (n - m) * len(string)
			print(count_1)
		if m >= n:
			a_1 = 0
			b_1 = 0
			count_1 = 0
			for i in string * n:
				if i == 'a':
					a_1 += 1
				else:
					b_1 += 1
				if a_1 > b_1:
					count_1 += 1
			print(count_1)
	if a < b:
		m = int(a / (b - a))
		m += 1
		a_1 = 0
		b_1 = 0
		count_1 = 0
		if n > m:
			for j in string * m:
				if j == 'a':
					a_1 += 1
				else:
					b_1 += 1
				if a_1 > b_1:
					count_1 += 1
			print(count_1)
		if m >= n:
			a_1 = 0
			b_1 = 0
			count_1 = 0
			for i in string * n:
				if i == 'a':
					a_1 += 1
				else:
					b_1 += 1
				if a_1 > b_1:
					count_1 += 1
			print(count_1)


T = int(input())

def f(m, st):
	v = 0
	k = m
	for i in st:
		if i == 'a':
			k += 1
		else:
			k -= 1
		if k > 0:
			v += 1
	return v
for something in range(T):
	(s, n) = input().split(' ')
	n = int(n)
	d = 0
	for i in s:
		if i == 'a':
			d += 1
		else:
			d -= 1
	ans = 0
	if d == 0:
		ans = f(0, s) * n
	elif d > 0:
		p = min(n, len(s) // (2 * abs(d)) + 3)
		for i in range(p):
			ans += f(i * d, s)
		ans += len(s) * (n - p)
	else:
		p = min(n, len(s) // (2 * abs(d)) + 3)
		for i in range(p):
			ans += f(i * d, s)
	print(ans)


from math import ceil
for _ in range(int(input())):
	(s, n) = input().split()
	n = int(n)
	slen = len(s)
	pre = [0] * slen
	ans = 0
	cnta = 0
	cntb = 0
	for i in range(slen):
		if s[i] == 'a':
			cnta += 1
		else:
			cntb += 1
		pre[i] = cnta - cntb
		if cnta > cntb:
			ans += 1
	diff = cnta - cntb
	if diff == 0:
		print(ans * n)
	elif diff > 0:
		ans = ans * n
		for i in range(slen):
			if pre[i] <= 0:
				canstop = ceil((-pre[i] + 1) / diff)
				ans += max(n - canstop, 0)
		print(ans)
	else:
		ans = 0
		for i in range(slen):
			if pre[i] > 0:
				canpropagate = ceil(-pre[i] / diff)
				ans += min(canpropagate, n)
		print(ans)


t = int(input())

def count(s, n=1):
	a = 0
	b = 0
	c = 0
	for j in range(n):
		for i in range(len(s)):
			if s[i] == 'a':
				a += 1
			elif s[i] == 'b':
				b += 1
			if a > b:
				c += 1
	return (c, a, b)
for x in range(t):
	temp = input().split(' ')
	(n, s) = (int(temp[1]), temp[0])
	size = len(s)
	(_, a, b) = count(s)
	if b > a:
		n1 = int((1 + b) / (b - a) + 1) + 1
		n1 = min(n1, n)
		(c, _, _) = count(s, n1)
		print(c)
	elif a > b:
		n1 = int((1 + b) / (a - b) + 1) + 1
		n1 = min(n1, n)
		(c, _, _) = count(s, n1)
		ans = c + size * (n - n1)
		print(ans)
	else:
		(init, _, _) = count(s)
		ans = init * n
		print(ans)


t = int(input())
for _ in range(t):
	(s, n) = input().split()
	ns = len(s)
	n = int(n)
	na = 0
	nb = 0
	total = 0
	while n:
		count = 0
		for i in s:
			if i == 'a':
				na += 1
			else:
				nb += 1
			if na > nb:
				count += 1
		total += count
		if na == nb:
			total = n * count
			break
		if count == 0:
			break
		n -= 1
		if count == ns:
			total += n * ns
			break
	print(total)


t = int(input())
for _ in range(t):
	li = list(map(str, input().split()))
	s = li[0]
	n = int(li[1])
	l = len(s)
	(a, b) = (0, 0)
	total = 0
	while n > 0:
		count = 0
		for i in s:
			if i == 'a':
				a += 1
			else:
				b += 1
			if a > b:
				count += 1
		total += count
		if a == b:
			total = n * count
			break
		if count == 0:
			break
		n -= 1
		if count == l:
			total += n * l
			break
	print(total)


t = int(input())
for _ in range(t):
	(s, n) = input().split()
	n = int(n)
	s = str(s)
	l = len(s)
	freqa = 0
	freqb = 0
	freq = 0
	f1 = 0
	f2 = 0
	for i in range(n):
		tempfreq = 0
		for j in range(len(s)):
			if s[j] == 'a':
				freqa += 1
			elif s[j] == 'b':
				freqb += 1
			if freqa > freqb:
				freq += 1
				tempfreq += 1
		if freqa == freqb:
			f1 = 1
			break
		if tempfreq == len(s):
			f2 = 1
			break
		if tempfreq == 0:
			break
	if f1:
		print(freq * n)
	elif f2:
		print(freq + (n - i - 1) * len(s))
	else:
		print(freq)


def fun():
	n = int(input())
	for a0 in range(n):
		a = list(input().split())
		s = a[0]
		m = int(a[1])
		l = len(s)
		arr = [0 for i in range(l)]
		count = 0
		for i in range(l):
			if s[i] == 'a':
				count += 1
			else:
				count -= 1
			arr[i] = count
		tot = count
		num = 0
		if tot == 0:
			for i in range(l):
				if arr[i] > 0:
					num += m
			print(num)
			continue
		elif tot < 0:
			for i in range(l):
				if arr[i] > 0:
					mi = arr[i]
					if mi % tot == 0:
						mi = mi // -tot
					else:
						mi = mi // -tot
						mi += 1
					if mi <= m:
						num = num + mi
					else:
						num = num + m
			print(num)
		else:
			for i in range(l):
				if arr[i] > 0:
					num = num + m
				else:
					mi = -arr[i]
					mi //= tot
					mi += 1
					mi = m - mi
					if mi > 0:
						num += mi
			print(num)
fun()


T = int(input())
for _ in range(T):
	(s, n) = input().strip().split()
	n = int(n)
	v = []
	p = 0
	tot = 0
	for c in s:
		if c == 'a':
			tot += 1
		else:
			tot -= 1
		v.append(tot)
		if tot > 0:
			p += 1
	vs = sorted(v)
	seuil = []
	prev = vs[0] - 1
	for i in range(len(vs)):
		if vs[i] != prev:
			seuil.append(len(vs) - i)
			prev = vs[i]
	seuil.append(0)
	if v[-1] == 0:
		print(p * n)
	else:
		fin = v[-1]
		deb = vs[0] - 1
		for i in range(n - 1):
			idx = -deb - fin
			if idx < 0:
				idx = 0
			elif idx >= len(seuil):
				idx = -1
			p = p + seuil[idx]
			if idx == -1 or idx == 0:
				break
			fin += v[-1]
		if idx == 0 and i < n - 2:
			p = p + (n - 2 - i) * seuil[idx]
		print(p)


T = int(input())
for t in range(T):
	(S, N) = input().split(' ')
	N = int(N)
	l = len(S)
	(count, countA, countB) = (0, 0, 0)
	answer = 0
	for n in range(N):
		count = 0
		for i in range(l):
			if S[i] == 'a':
				countA += 1
			else:
				countB += 1
			if countA > countB:
				count += 1
		if count == 0:
			break
		elif count == l or countA == countB:
			answer += (N - n) * count
			break
		else:
			answer += count
	print(answer)


t = int(input())
for i in range(t):
	(a, k) = map(str, input().split(' '))
	hash1 = [0, 0]
	k = int(k)
	ans = 0
	a1 = 0
	b1 = 0
	for j in range(k):
		count = 0
		for l in range(len(a)):
			if a[l] == 'a':
				a1 += 1
			else:
				b1 += 1
			if a1 > b1:
				count += 1
		if count == 0:
			break
		elif count == len(a):
			ans = ans + (k - j) * count
			break
		elif a1 == b1:
			ans += (k - j) * count
			break
		else:
			ans += count
	print(ans)


from sys import stdin
from math import ceil
for _ in range(int(stdin.readline().strip())):
	(s, n) = stdin.readline().split()
	n = int(n)
	score = 0
	arr = []
	for ch in s:
		if ch == 'a':
			score += 1
		else:
			score -= 1
		arr.append(score)
	single = arr[-1]
	if single == 0:
		positives = 0
		for i in arr:
			if i > 0:
				positives += 1
		print(n * positives)
	elif single < 0:
		rounds_positive = []
		for i in arr:
			if i > 0:
				num = ceil(i / -single)
				if num > n:
					num = n
			else:
				num = 0
			rounds_positive.append(num)
		print(sum(rounds_positive))
	else:
		rounds_positive = []
		for i in arr:
			if i > 0:
				num = n
			else:
				num = n - 1 - -i // single
				if num < 0:
					num = 0
			rounds_positive.append(num)
		print(sum(rounds_positive))


pr = int(input())
for kui in range(0, pr):
	(s, n) = map(str, input().strip().split(' '))
	mi = int(n)
	oi = mi
	p = len(s)
	j = s
	k = [0]
	(c, x, y, w, v, z) = (0, 0, 0, 0, 0, 0)
	while v != 1:
		for i in range(z, len(s)):
			t = s[i]
			if t == 'a':
				x = x + 1
			else:
				y = y + 1
			if x > y:
				c = c + 1
			p = p - 1
			if p == 0:
				if c == k[len(k) - 1]:
					v = 1
					break
				k.append(c)
				w = w + 1
				c = 0
				p = len(j)
		mi = mi - 1
		if mi != 0:
			z = len(s)
			s = s + j
		else:
			v = 1
	oi = oi - w
	f = c * oi + sum(k)
	print(f)


def ans(s):
	ca = s.count('a')
	cb = s.count('b')
	count = 0
	for j in range(len(s) - 1, -1, -1):
		if s[j] == 'a':
			ca -= 1
		if s[j] == 'b':
			cb -= 1
		if ca > cb:
			count += 1
	return count
t = int(input())
for _ in range(t):
	(s, n) = input().split()
	n = int(n)
	ca = s.count('a')
	cb = s.count('b')
	if ca == cb:
		print(ans(s) * n)
	elif ca < cb:
		a = ca
		b = cb
		k = 2
		while cb / b < n:
			if cb - ca > a:
				break
			else:
				ca = a * k
				cb = b * k
				k += 1
		x = cb // b
		if x > n:
			x = n
		temp = s
		for j in range(1, x):
			s += temp
		print(ans(s))
	elif ca > cb:
		if n > 1:
			a = ca
			b = cb
			k = 2
			while ca // a < n:
				if ca - cb > b:
					break
				else:
					ca = a * k
					cb = b * k
					k += 1
			x = ca // a
			if x > n:
				x = n
			temp = s
			for j in range(1, x):
				s += temp
			print((n - x) * len(temp) + ans(s) + 1)
		else:
			print(ans(s) + 1)


for _ in range(int(input())):
	(s, n) = input().split()
	n = int(n)
	good_prefix_count = 0
	a_count = 0
	s_score = 2 * s.count('a') - len(s)
	for c in s:
		if c == 'a':
			a_count += 1
		else:
			a_count -= 1
		if s_score < 0:
			good_prefix_count += min(n, max(0, (1 - a_count) // s_score + 1))
		elif s_score > 0:
			good_prefix_count += min(n, max(0, (a_count - 1) // s_score + n))
		elif a_count > 0:
			good_prefix_count += n
	print(good_prefix_count)


t = int(input())
while t > 0:
	(string, n) = input().split()
	n = int(n)
	counta = 0
	countb = 0
	count = 0
	for i in range(len(string)):
		if string[i] == 'a':
			counta += 1
		elif string[i] == 'b':
			countb += 1
		if counta > countb:
			count += 1
	if countb == counta:
		count = count * n
	elif counta > countb:
		length = len(string)
		prevcount = count
		individualcount = count
		num = 1
		while length != individualcount:
			if num == n:
				break
			for i in range(len(string)):
				if string[i] == 'a':
					counta += 1
				elif string[i] == 'b':
					countb += 1
				if counta > countb:
					count += 1
			individualcount = count - prevcount
			prevcount = count
			num += 1
		count = count + (n - num) * length
	else:
		prevcount = count
		individualcount = count
		m = n - 1
		while individualcount != 0:
			if m == 0:
				break
			for i in range(len(string)):
				if string[i] == 'a':
					counta += 1
				elif string[i] == 'b':
					countb += 1
				if counta > countb:
					count += 1
			individualcount = count - prevcount
			prevcount = count
			m -= 1
	print(count)
	t -= 1


T = int(input())
while T > 0:
	(s, m) = input().split()
	m = int(m)
	ca = 0
	cb = 0
	w = 0
	yes = 0
	caa = 0
	cap = 0
	we = 0
	for j in range(m):
		cap = caa
		caa = 0
		wee = we
		we = 0
		for i in range(len(s)):
			if s[i] == 'a':
				ca += 1
				caa += 1
			else:
				cb += 1
			if ca > cb:
				w += 1
				we += 1
		if we == wee:
			yes = 1
			break
	if yes == 0:
		print(w)
	else:
		print(w + we * (m - j - 1))
	T -= 1


d = {'a': 1, 'b': -1}
T = int(input())
for t in range(T):
	(s, n) = input().split()
	n = int(n)
	cur = 0
	cnt = []
	for ch in s:
		cur += d[ch]
		cnt.append(cur)
	delta = cnt[-1]
	res = 0
	if delta == 0:
		res = n * sum(map(lambda x: x > 0, cnt))
	elif delta < 0:
		for v in cnt:
			if v > 0:
				res -= max(-n, v // delta)
	else:
		for v in cnt:
			res += n
			if v <= 0:
				res -= min(n, -v // delta + 1)
	print(res)


for _ in range(int(input())):
	(s, n) = input().split()
	n = int(n)
	l = []
	length = len(s)
	(actr, pos_ctr, ans) = (0, 0, 0)
	(po_ctr, ne_ctr) = (0, 0)
	for i in range(length):
		if s[i] == 'a':
			actr += 1
		else:
			actr -= 1
		l.append(actr)
		if actr > 0:
			pos_ctr += 1
	rem_count = 0
	if l[-1] == 0 or pos_ctr == length:
		print(pos_ctr * n)
	else:
		while po_ctr != length and ne_ctr != length:
			(po_ctr, ne_ctr) = (0, 0)
			rem_count += 1
			temp = l[-1]
			for i in range(length):
				if s[i] == 'a':
					temp += 1
				else:
					temp -= 1
				l.append(temp)
				if temp > 0:
					po_ctr += 1
				else:
					ne_ctr += 1
		if po_ctr == length:
			if rem_count + 1 < n:
				ans = (n - rem_count) * length
				for i in range(len(l) - length):
					if l[i] > 0:
						ans += 1
			elif rem_count + 1 == n:
				ans = pos_ctr
				for i in range(length, len(l)):
					if l[i] > 0:
						ans += 1
			else:
				ans = 0
				for i in range(n * length):
					if l[i] > 0:
						ans += 1
		elif ne_ctr == length:
			if rem_count + 1 < n:
				ans = 0
				for i in range(len(l) - length):
					if l[i] > 0:
						ans += 1
			elif rem_count + 1 == n:
				ans = pos_ctr
				for i in range(length, len(l) - length):
					if l[i] > 0:
						ans += 1
			else:
				for i in range(n * length):
					if l[i] > 0:
						ans += 1
		print(ans)


def countpre(s, n, l):
	a0 = 0
	b0 = 0
	a = 0
	b = 0
	c = 0
	for i in s:
		if i == 'a':
			a += 1
			a0 += 1
		else:
			b += 1
			b0 += 1
		if a > b:
			c += 1
	if a0 == b0:
		return c * n
	for j in range(1, n):
		for i in s:
			if i == 'a':
				a += 1
			else:
				b += 1
			if a > b:
				c += 1
		if a > b + b0:
			return c + l * (n - 1 - j)
		elif b > a + a0:
			return c
	return c
T = int(input())
while T:
	T -= 1
	(s, n) = input().split()
	print(countpre(s, int(n), len(s)))


z = int(input())
while z:
	z -= 1
	x = input().split()
	s = x[0]
	n = int(x[1])
	(ca, cb, p, ga, gb, res, t) = (0, 0, 0, 0, 0, 0, 0)
	for c in s:
		if c == 'a':
			ca = ca + 1
		else:
			cb = cb + 1
	diff = ca - cb
	if diff > 0:
		for q in range(n):
			p = 0
			for c in s:
				if c == 'a':
					ga = ga + 1
				else:
					gb = gb + 1
				if ga > gb:
					p += 1
			if p == len(s):
				t = q + 1
				res = res + p
				break
			res = res + p
		if t != 0:
			total = res + (n - t) * len(s)
		else:
			total = res
	elif diff < 0:
		for q in range(n):
			p = 0
			for c in s:
				if c == 'a':
					ga = ga + 1
				else:
					gb = gb + 1
				if ga > gb:
					p += 1
			if p == 0:
				res = res + p
				break
			res = res + p
		total = res
	else:
		for c in s:
			if c == 'a':
				ga = ga + 1
			else:
				gb = gb + 1
			if ga > gb:
				p += 1
		total = p * n
	print(total)


def mp():
	return map(str, input().split(' '))

def lst():
	return list(mp())
for w in range(int(input())):
	(s, k) = mp()
	k = int(k)
	c = p = ans = 0
	b = []
	for i in range(len(s)):
		if s[i] == 'a':
			c += 1
			b.append(c)
			if c > 0:
				p += 1
		else:
			c -= 1
			b.append(c)
			if c > 0:
				p += 1
	if c > 0 and p == len(s):
		ans = len(s) * k
		print(ans)
	elif c <= 0 and p == 0:
		print(0)
	elif c > 0:
		j = m = 0
		for i in range(len(b)):
			if b[i] <= 0:
				m = 1 + abs(b[i]) // c
				if m > k:
					m = k
				j += m
		ans = k * len(b) - j
		print(ans)
	elif c < 0:
		j = m = 0
		c = abs(c)
		for i in range(len(b)):
			if b[i] > 0 and b[i] % c == 0:
				m = b[i] // c
				if m > k:
					m = k
				j += m
			elif b[i] > 0 and b[i] % c != 0:
				m = 1 + b[i] // c
				if m > k:
					m = k
				j += m
		print(j)
	elif c == 0:
		print(p * k)


import math
t = int(input())
while t:
	t = t - 1
	(s, n) = input().split()
	slen = len(s)
	score = [0] * slen
	n = int(n)
	noa = 0
	nob = 0
	iterate = 0
	temp_iterate = 0
	for i in s:
		if i == 'a':
			noa = noa + 1
			score[iterate] = temp_iterate + 1
			temp_iterate = score[iterate]
			iterate = iterate + 1
		elif i == 'b':
			nob = nob + 1
			score[iterate] = temp_iterate - 1
			temp_iterate = score[iterate]
			iterate = iterate + 1
	diff = noa - nob
	count = 0
	for i in score:
		if diff > 0:
			if i <= 0:
				diff_zero = 0 - i
				rep = diff_zero // diff + 1
				if n > rep:
					count = count - rep + n
			if i > 0:
				count = count + n
		elif diff < 0:
			if i > 0:
				rep = math.ceil(i / (0 - diff))
				if rep < n:
					count = count + rep
				else:
					count = count + n
		elif i > 0:
			count = count + n
	print(count)


import math
t = int(input())
for _ in range(t):
	(s, n) = input().strip().split(' ')
	n = int(n)
	size = len(s)
	a = [0] * size
	summ = 0
	ans = 0
	for i in range(size):
		if s[i] == 'a':
			summ += 1
		else:
			summ -= 1
		a[i] = summ
	if summ > 0:
		for i in a:
			if i > 0:
				ans += n
			else:
				ans += max(0, n - int(math.ceil((1 - i) / summ)))
	elif summ < 0:
		for i in a:
			if i > 0:
				ans += min(max(0, int(math.ceil((0 - i) / summ))), n)
	else:
		for i in a:
			if i > 0:
				ans += n
	print(ans)


test = int(input())
for i in range(test):
	res = input().split()
	les = len(res[0])
	dic = {}
	dic['a'] = 0
	dic['b'] = 0
	m = 0
	for i in res[0]:
		if i == 'a':
			dic['a'] = dic['a'] + 1
			if dic['a'] > dic['b']:
				m = m + 1
		else:
			dic['b'] = dic['b'] + 1
			if dic['a'] > dic['b']:
				m = m + 1
	k = dic['a'] - dic['b']
	j = 0
	l = 0
	while j < int(res[1]) - 1:
		count = 0
		for i in res[0]:
			if i == 'a':
				k = k + 1
				if k > 0:
					count = count + 1
			else:
				k = k - 1
				if k > 0:
					count = count + 1
		if k == 0:
			l = count
			break
		elif count == les:
			break
		elif count == 0:
			break
		else:
			l = l + count
			j = j + 1
	if dic['a'] < dic['b']:
		print(m + l)
	elif dic['a'] == dic['b']:
		print(m + l * (int(res[1]) - 1))
	else:
		print(m + l + les * (int(res[1]) - 1 - j))


t = int(input())
for i in range(t):
	(s, w) = input().split()
	w = int(w)
	temp = w
	total = 0
	co = 0
	nc = 0
	pco = 0
	j = 0
	while j <= len(s):
		if j == len(s):
			w = w - 1
			diff = co - pco
			pco = co
			co = nc
			if temp - w >= 3:
				if diff == co - pco:
					break
			j = 0
		if w == 0:
			break
		if s[j] == 'a':
			total = total + 1
		elif s[j] == 'b':
			total = total - 1
		if total > 0:
			nc = nc + 1
		j = j + 1
	nc = nc + diff * w
	print(nc)


T = int(input())
for t in range(T):
	(s, K) = input().split()
	pomd = len(s)
	K = int(K)
	pom = True
	pa = 0
	pb = 0
	p = 0
	pomk = 0
	pomp = 0
	while pom:
		for z in s:
			if z == 'a':
				pa += 1
			else:
				pb += 1
			if pa > pb:
				p += 1
				pomp += 1
		pomk += 1
		if pa == pb:
			pom = False
			p = p * K
		if pomp == pomd:
			pom = False
			p = p + (K - pomk) * pomd
		if pomp == 0:
			pom = False
		if pomk == K:
			pom = False
		pomp = 0
	print(p)


T = int(input())
ans = []
for xx in range(T):
	c = 0
	d = dict({'a': 0, 'b': 0})
	(s, zz) = map(str, input().split())
	n = int(zz)
	i = 0
	c1 = 0
	c2 = 0
	flag = 1
	while i < n:
		c2 = c1
		c1 = 0
		for k in s:
			d[k] = d[k] + 1
			if d['a'] > d['b']:
				c1 = c1 + 1
		if c1 == 0:
			break
		if c1 == c2:
			flag = 0
			break
		c = c + c1
		i = i + 1
	if flag == 0:
		c = c + (n - i) * c2
	ans.append(c)
for k in ans:
	print(k)


t = int(input())
for idx in range(t):
	ans = 0
	e = 0
	a = input().split()
	n = int(a[1])
	s = a[0]
	i = 0
	dif = 0
	co = 0
	pco = 0
	temp = n
	while i >= 0:
		if i == len(s):
			n = n - 1
			dif = co - pco
			pco = co
			co = ans
			if temp - n >= 3:
				if dif == co - pco:
					break
			i = 0
		if n == 0:
			break
		if s[i] == 'a':
			e = e + 1
		else:
			e = e - 1
		if e > 0:
			ans = ans + 1
		i = i + 1
	print(ans + dif * n)


for z in range(int(input())):
	(s, n) = [x for x in input().split()]
	n = int(n)
	np = n
	k = 0
	l = 0
	ca = 0
	cb = 0
	agg = 0
	prev = -1
	flag = 0
	while n != 0:
		cp = 0
		k += 1
		for i in range(len(s)):
			if s[i] == 'a':
				ca += 1
			else:
				cb += 1
			if ca > cb:
				cp += 1
		if prev == cp:
			break
		else:
			agg += cp
			prev = cp
		n -= 1
	if n == 0:
		print(agg)
	else:
		l = (np - (k - 1)) * cp
		print(agg + l)


t = int(input())
for _ in range(t):
	(s, n) = input().split()
	n = int(n)
	l = len(s)
	c = [0] * l
	b = [0] * l
	s1 = 0
	s2 = 0
	for i in range(l):
		if s[i] == 'a':
			s1 += 1
		else:
			s1 -= 1
		if s1 > 0:
			c[i] = 1
		b[i] = s1
	last = b[-1]
	if last == 0:
		s2 = sum(c) * n
	elif last > 0:
		for i in b:
			if i > 0:
				s2 += n
			elif i == 0:
				s2 += n - 1
			else:
				s2 += max(0, n - (-i // last + 1))
	else:
		for i in b:
			if i <= 0:
				s2 += 0
			else:
				s2 += 1
				m1 = -i / last
				m = -i // last
				if m == m1:
					m -= 1
				s2 += min(n - 1, m)
	print(s2)


from itertools import accumulate
from bisect import bisect_left
t = int(input())
for _ in range(t):
	(s, n) = input().split()
	n = int(n)
	a = list(accumulate(((c == 'b') - (c == 'a') for c in s)))
	t = -a[-1]
	a.sort()
	if t == 0:
		print(n * bisect_left(a, 0))
	else:
		m = max(0, min(n, a[(0, -1)[t > 0]] // t + 1))
		ans = sum((bisect_left(a, t * i) for i in range(m)))
		if t > 0:
			ans += len(s) * (n - m)
		print(ans)


from math import *
t = int(input())
for test in range(t):
	(s, n) = input().split()
	n = int(n)
	s_len = len(s)
	a = [0] * s_len
	b = [0] * s_len
	if s[0] == 'a':
		a[0] = 1
	else:
		b[0] = 1
	for i in range(1, s_len):
		if s[i] == 'a':
			a[i] = a[i - 1] + 1
			b[i] = b[i - 1]
		else:
			a[i] = a[i - 1]
			b[i] = b[i - 1] + 1
	ans = 0
	if a[s_len - 1] < b[s_len - 1]:
		for i in range(s_len):
			if a[i] > b[i]:
				ans += max(min(ceil((a[i] - b[i]) / (b[s_len - 1] - a[s_len - 1])) - 1, n - 1), -1) + 1
	elif a[s_len - 1] > b[s_len - 1]:
		for i in range(s_len):
			ans += n - min(max(floor((b[i] - a[i]) / (a[s_len - 1] - b[s_len - 1])) + 1, 0), n)
	elif a[s_len - 1] == b[s_len - 1]:
		for i in range(s_len):
			if a[i] > b[i]:
				ans += n
	print(ans)


import numpy as np
t = int(input())
for _ in range(t):
	(s, s2) = input().split()
	n = int(s2)
	A = np.array([1 if c == 'a' else -1 for c in s], dtype=np.int64)
	B = np.cumsum(A, dtype=np.int64)
	x = np.sum(B > 0)
	(minB, maxB, last) = (min(B), max(B), B[-1])
	if last == 0:
		print(x * n)
	elif last < 0:
		if maxB <= 0:
			print(0)
		else:
			first_cnt = maxB // -last + 1
			if first_cnt > n:
				first_cnt = n
			A = np.array(list(A) * first_cnt, dtype=np.float64)
			B = np.cumsum(A, dtype=np.float64)
			print('%d' % np.sum(B > 0))
	elif minB > 0:
		print(len(s) * n)
	elif minB == 0:
		print(x + len(s) * (n - 1))
	else:
		first_cnt = -minB // last + 1
		if first_cnt > n:
			first_cnt = n
		A = np.array(list(A) * first_cnt, dtype=np.float64)
		B = np.cumsum(A, dtype=np.float64)
		x = np.sum(B > 0, dtype=np.float64)
		x += float(n - first_cnt) * len(s)
		print('%d' % x)


from math import *
for i in range(int(input())):
	(s, n) = list(map(str, input().split()))
	k = int(n)
	tem = []
	tum = []
	(a, count) = (0, 0)
	for i in s:
		if i == 'a':
			a += 1
			tem.append(1)
		else:
			a -= 1
			tem.append(-1)
		tum.append(a)
		if a >= 1:
			count += 1
	ma = max(tum)
	mi = min(tum)
	if a == 0:
		ans = count * k
	elif a > 0:
		if mi > 0:
			ans = count * k
		else:
			cd = a
			for j in range(len(s), k * len(s)):
				if j % len(s) == 0:
					mi = mi + cd
				a = a + tem[j % len(s)]
				if a > 0:
					count += 1
				if mi > 0:
					break
			if k != 1:
				ans = count + k * len(s) - j - 1
			else:
				ans = count
	elif ma < 1:
		ans = count
	else:
		cd = a
		for j in range(len(s), k * len(s)):
			if j % len(s) == 0:
				ma = ma + cd
			a = a + tem[j % len(s)]
			if a > 0:
				count += 1
			if ma <= 0:
				break
		ans = count
	print(ans)


T = int(input())
for i in range(T):
	arr = []
	(arr, N) = input().split()
	arr = list(arr)
	N = int(N)
	countA = 0
	countB = 0
	count = 0
	length = len(arr)
	if N <= 3:
		flag = 0
		for j in range(N):
			for k in range(length):
				if arr[k] == 'a':
					countA += 1
				else:
					countB += 1
				if countA > countB:
					count += 1
		print(count)
	else:
		flag = 0
		countT = 0
		for j in range(N):
			c = 0
			for k in range(length):
				if arr[k] == 'a':
					countA += 1
				else:
					countB += 1
				if countA > countB:
					count += 1
					c += 1
			if countT == c:
				print(count + c * (N - j - 1))
				flag = 1
				break
			countT = c
		if flag == 0:
			print(count)


def func(string, n):
	lensum = 0
	a = 0
	b = 0
	aup = []
	adn = []
	arr = [0] * len(string)
	cp = 0
	count = 0
	for i in range(0, len(string)):
		if string[i] == 'a':
			lensum = lensum + 1
			a += 1
		if string[i] == 'b':
			lensum = lensum - 1
			b += 1
		arr[i] = lensum
	for i in range(0, len(arr)):
		if arr[i] > 0:
			cp += 1
	if a > b:
		for i in range(0, len(string)):
			itr = int(1 - arr[i] / lensum)
			itr = max(itr, 0)
			while itr > 0:
				if (itr - 1) * lensum + arr[i] > 0:
					itr = itr - 1
				else:
					break
			aup.append(itr)
		answer = [max(n - x, 0) for x in aup]
		for i in range(0, len(string)):
			if answer[i] > 0:
				count = count + min(n, answer[i])
		return count
	if b > a:
		for i in range(0, len(string)):
			itr = int(1 - arr[i] / lensum) - 1
			itr = max(itr, 0)
			while itr + 1 <= n:
				if itr * lensum + arr[i] > 0:
					itr = itr + 1
				else:
					break
			adn.append(max(0, itr))
		for i in range(0, len(string)):
			count += min(n, adn[i])
		return count
	if b == a:
		answer = cp * n
		return answer
t = int(input())
for q in range(0, t):
	(s, n) = input().split()
	n = int(n)
	print(func(s, n))


for _ in range(int(input())):
	a = [x for x in input().split()]
	(co, b, char_a) = (0, [0] * len(a[0]), 0)
	for i in range(len(a[0])):
		char_a += 1 if a[0][i] == 'a' else -1
		b[i] = char_a
	if char_a > 0:
		for i in range(len(a[0])):
			temp = 0
			while b[i] <= 0 and temp < int(a[1]):
				b[i] += char_a
				temp += 1
			co += int(a[1]) - temp
	elif char_a < 0:
		for i in range(len(a[0])):
			temp = 0
			while b[i] > 0 and temp < int(a[1]):
				b[i] += char_a
				temp += 1
			co += temp
	else:
		for i in range(len(a[0])):
			if b[i] > 0:
				co += int(a[1])
	print(co)


for i in range(int(input())):
	s = list(map(str, input().split()))
	s[1] = float(s[1])
	length = len(s[0])
	arr = []
	a = 0
	b = 0
	ans = 0
	for j in range(length):
		if s[0][j] == 'a':
			a = a + 1
		else:
			a = a - 1
		if a > 0:
			b = b + 1
		arr.append(a)
	if arr[length - 1] < 0:
		for k in range(length):
			if arr[k] <= 0:
				ans = ans + 0
			else:
				x = -arr[k] / arr[length - 1] + 1
				if x > s[1]:
					ans = ans + s[1]
				elif x > int(x):
					x = int(x) + 1
					ans = ans + x - 1
				else:
					ans = ans + x - 1
	elif arr[length - 1] == 0:
		ans = b * s[1]
	else:
		for k in range(length):
			if arr[k] > 0:
				ans = ans + s[1]
			else:
				x = (1 - arr[k]) / arr[length - 1] + 1
				if x > s[1]:
					ans = ans + 0
				elif x > int(x):
					x = int(x) + 1
					ans = ans + s[1] - x + 1
				else:
					ans = ans + s[1] - x + 1
	print(int(ans))


from math import *
t = int(input().strip())
for i in range(t):
	(s, n) = input().strip().split(' ')
	n = int(n)
	l = list(s)
	c = l.count('a')
	b = l.count('b')
	d = c - b
	l1 = []
	v = 0
	sum = 0
	k = 0
	for i in s:
		if i == 'a':
			sum += 1
		else:
			sum -= 1
		if sum > 0:
			v += 1
		l1.append(sum)
	if c == b:
		print(v * n)
	elif b > c:
		if v > 0:
			for i in l1:
				if i > 0:
					j = i + (n - 1) * (c - b)
					if j < 1:
						k += ceil(i / (b - c))
					else:
						k += int((i - j) / (b - c)) + 1
			print(k)
		else:
			print('0')
	else:
		for i in range(len(l1)):
			if l1[i] >= 1:
				k += n
			else:
				l[i] = l1[i] + (n - 1) * d
				if l[i] >= 1:
					k += ceil(l[i] / d)
		print(k)


for i in range(int(input())):
	(x, y) = input().split()
	d = {}
	a = 0
	b = 0
	l = 0
	for i in range(len(x)):
		if x[i] == 'a':
			a += 1
		else:
			b += 1
		if a - b > 0:
			l += 1
		if b - a in d:
			d[b - a] += 1
		else:
			d[b - a] = 1
	v = list(d.items())
	max = 0
	min = 0
	sum = l
	m = l
	g = 0
	q = 0
	n = a - b
	for i in range(len(v)):
		if v[i][0] > max:
			max = v[i][0]
		if min == 0:
			min = v[i][0]
		if min != 0 and v[i][0] < min:
			min = v[i][0]
	if a - b != 0:
		z = max / n
		h = min / n
	if l == 0:
		print(0)
	elif n == 0:
		print(l * int(y))
	elif n > 0:
		for i in range(1, int(y)):
			if i <= z:
				for j in range(len(v)):
					if v[j][0] < i * n and v[j][0] >= (i - 1) * n:
						m += v[j][1]
			elif i > z:
				g = (int(y) - i) * len(x)
				sum += g
				break
			sum += m
		print(sum)
	elif n < 0:
		for i in range(1, int(y)):
			if i <= h:
				for j in range(len(v)):
					if v[j][0] >= i * n and v[j][0] < (i - 1) * n:
						m -= v[j][1]
			elif i > h:
				break
			sum += m
		print(sum)


t = int(input())
while t > 0:
	t = t - 1
	(s, n) = input().split()
	n = int(n)
	le = len(s)
	a = []
	b = []
	x = 0
	y = 0
	d = 0
	c = 0
	ans = 0
	for i in range(le):
		if s[i] == 'a':
			x = x + 1
		elif s[i] == 'b':
			y = y + 1
		if y - x >= 0:
			a.append(y - x)
		else:
			b.append(x - y)
	d1 = x - y
	d2 = y - x
	if n == 1:
		print(le - len(a))
	elif d1 == 0:
		print(n * (le - len(a)))
	elif d1 < 0:
		for i in range(len(b)):
			c = int(b[i] / d2)
			if c * d2 == b[i]:
				c = c - 1
			if c < n:
				d = d + c
			else:
				d = d + n - 1
		print(d + len(b))
	else:
		for i in range(len(a)):
			c = int(a[i] / d1)
			if c < n:
				ans = ans + c
			else:
				ans = ans + n - 1
		print(n * le - ans - len(a))


from math import ceil
T = int(input())
for test_case in range(T):
	(s, n) = input().split()
	n = int(n)
	dn = dict()
	dp = dict()
	offset = 0
	ans = 0
	for i in s:
		if i == 'a':
			offset += 1
		else:
			offset -= 1
		if offset > 0:
			ans += 1
			try:
				dp[offset] += 1
			except KeyError:
				dp[offset] = 1
		else:
			try:
				dn[offset] += 1
			except KeyError:
				dn[offset] = 1
	ans *= n
	if offset > 0:
		for i in dn:
			n1 = n - 1 - int(abs(i) / offset)
			if n1 > 0:
				ans += n1 * dn[i]
	elif offset < 0:
		for i in dp:
			n1 = n - ceil(i / abs(offset))
			if n1 > 0:
				ans -= n1 * dp[i]
	print(ans)


t = int(input())
for z in range(t):
	(s, n) = input().split()
	n = int(n)
	los = len(s)
	AuxArr = [0] * los
	DiffArr = [0] * los
	AuxArr[0] = 1
	if s[0] == 'b':
		AuxArr[0] = -1
	for i in range(1, los):
		if s[i] == 'a':
			AuxArr[i] = AuxArr[i - 1] + 1
		else:
			AuxArr[i] = AuxArr[i - 1] - 1
	cArr = [0] * los
	director = AuxArr[-1]
	ans = 0
	if director == 0:
		for e in AuxArr:
			if e > 0:
				ans += 1
		ans = ans * n
	elif director > 0:
		for i in range(los):
			if AuxArr[i] <= 0:
				cArr[i] = abs(AuxArr[i]) // director + 1
		for i in range(los):
			ans += max(0, n - cArr[i])
	else:
		director = -director
		for i in range(los):
			if AuxArr[i] > 0:
				cArr[i] = (AuxArr[i] - 1) // director + 1
		for i in range(los):
			ans += min(n, cArr[i])
	print(ans)


t = int(input())
ans = []
while t > 0:
	sn = input().split()
	s = sn[0]
	n = int(sn[1])
	count_a = 0
	count_b = 0
	count = 0
	pattern = 0
	pattern_count = 0
	iteration = 0
	while True and iteration < n:
		iteration = iteration + 1
		single_count = 0
		for x in s:
			if x == 'a':
				count_a = count_a + 1
			elif x == 'b':
				count_b = count_b + 1
			if count_a > count_b:
				count = count + 1
				single_count = single_count + 1
		if pattern == single_count:
			count = count + (n - iteration) * single_count
			break
		else:
			pattern = single_count
	ans.append(count)
	t = t - 1
for x in ans:
	print(x)


t = int(input())
while t:
	s = input()
	given_string = s.split()[0]
	n = int(s.split()[1])
	la = 0
	lb = 0
	c1 = 0
	for i in given_string:
		if i == 'a':
			la = la + 1
		else:
			lb = lb + 1
		if la > lb:
			c1 += 1
	c2 = c1
	for i in given_string:
		if i == 'a':
			la = la + 1
		else:
			lb = lb + 1
		if la > lb:
			c2 = c2 + 1
	diff = c2 - c1
	pre = c2
	n1 = 2
	if n > n1:
		while n1 <= n:
			n1 += 1
			for i in given_string:
				if i == 'a':
					la = la + 1
				else:
					lb = lb + 1
				if la > lb:
					c2 = c2 + 1
			if c2 - pre == diff:
				break
			diff = c2 - pre
			pre = c2
		print(c2 + (n - n1) * diff)
	elif n == 1:
		print(c1)
	else:
		print(c2)
	t = t - 1


for t in range(int(input())):
	(s, n) = input().split()
	n = int(n)
	a_count = s.count('a')
	b_count = s.count('b')
	a_temp = 0
	b_temp = 0
	count = 0
	if a_count == b_count:
		for i in s:
			if i == 'a':
				a_temp += 1
			else:
				b_temp += 1
			if a_temp > b_temp:
				count += 1
		count = count * n
		print(count)
	elif a_count > b_count:
		con = 0
		count_temp = 0
		l = []
		while a_temp - b_temp <= a_count:
			con += 1
			for i in s:
				if i == 'a':
					a_temp += 1
				else:
					b_temp += 1
				if a_temp > b_temp:
					count_temp += 1
			l.append(count_temp)
			if n == con:
				break
		if len(l) == 1:
			print(count_temp)
		else:
			count = count_temp + (l[-1] - l[-2]) * (n - con)
			print(count)
	else:
		con = 0
		count_temp = 0
		l = []
		while b_temp - a_temp <= b_count:
			con += 1
			for i in s:
				if i == 'a':
					a_temp += 1
				else:
					b_temp += 1
				if a_temp > b_temp:
					count_temp += 1
			l.append(count_temp)
			if n == con:
				break
		count = count_temp
		print(count)


t = int(input())
while t:
	t -= 1
	(s, n) = input().split()
	n = int(n)
	acount = s.count('a')
	bcount = s.count('b')
	total = 0
	c = 0
	if acount == bcount:
		for x in s:
			if x == 'a':
				c += 1
			else:
				c -= 1
			if c > 0:
				total += 1
		print(total * n)
	elif acount > bcount:
		scount = 1
		while c <= bcount and scount <= n:
			scount += 1
			for x in s:
				if x == 'a':
					c += 1
				else:
					c -= 1
				if c > 0:
					total += 1
		total += (n - scount + 1) * len(s)
		print(total)
	else:
		scount = 1
		while c + acount >= 0 and scount <= n:
			scount += 1
			for x in s:
				if x == 'a':
					c += 1
				else:
					c -= 1
				if c > 0:
					total += 1
		print(total)


t = int(input())
for _ in range(t):
	(s, n) = input().split()
	n = int(n)
	k = len(s)
	count = locale_count = a = b = 0
	m = 0
	for j in range(n):
		locale_count = 0
		for i in s:
			if i == 'a':
				a += 1
			else:
				b += 1
			if a > b:
				locale_count += 1
		count += locale_count
		if a == b:
			count += (n - 1) * locale_count
			break
		if locale_count == k or locale_count == 0:
			count += locale_count * (n - j - 1)
			break
	print(count)


for i in range(int(input())):
	(s, n) = input().split()
	n = int(n)
	a = []
	if s[0] == 'a':
		a.append(1)
	else:
		a.append(-1)
	for i in range(1, len(s)):
		if s[i] == 'a':
			a.append(1 + a[i - 1])
		else:
			a.append(-1 + a[i - 1])
	l = len(a)
	y = a[l - 1]
	if y == 0:
		res = len([x for x in a if x > 0])
		print(res * n)
	elif y < 0:
		res = len([x for x in a if x > 0])
		s1 = list(filter(lambda x: x + y > 0, a))
		c = 2
		m = n - 1
		while len(s1) > 0 and m > 0:
			res += len(s1)
			s1 = list(filter(lambda x: x + c * y > 0, s1))
			c += 1
			m -= 1
		print(res)
	elif y > 0:
		res = len([x for x in a if x <= 0])
		s1 = list(filter(lambda x: x + y <= 0, a))
		c = 2
		m = n - 1
		while len(s1) > 0 and m > 0:
			res += len(s1)
			s1 = list(filter(lambda x: x + c * y <= 0, s1))
			c += 1
			m -= 1
		print(n * len(s) - res)


for _ in range(int(input())):
	(s, n) = input().split()
	l = len(s)
	A = s.count('a')
	B = l - A
	ans = 0
	n = int(n)
	if A == B:
		a = 0
		b = 0
		for i in range(l):
			if s[i] == 'a':
				a += 1
				if a > b:
					ans += 1
			else:
				b += 1
				if a > b:
					ans += 1
		ans = ans * n
	else:
		a = 0
		b = 0
		ans = 0
		for i in range(n):
			for j in range(l):
				if s[j] == 'a':
					a += 1
					if a > b:
						ans += 1
				else:
					b += 1
					if a > b:
						ans += 1
			if a - b > B:
				ans += (n - i - 1) * l
				break
			elif b - a > A:
				break
	print(ans)


t = int(input())
for i in range(t):
	temp = input().strip().split()
	s = temp[0]
	l = len(s)
	n = int(temp[1])
	freq = {'a': 0, 'b': 0}
	count = 0
	i = 0
	constancy_check = [0]
	counts_tracker = [0]
	index = -1
	cycles = 0
	while index < l:
		if cycles == n:
			break
		index = index + 1
		c = s[index]
		freq[c] += 1
		if freq['a'] > freq['b']:
			count = count + 1
		if i == l - 1:
			i = 0
			cycles = cycles + 1
			index = -1
			constancy_check.append(count - counts_tracker[-1])
			counts_tracker.append(count)
			if constancy_check[-1] == constancy_check[-2]:
				break
		else:
			i = i + 1
	count = count + (n - len(constancy_check) + 1) * constancy_check[-1]
	print(count)


import math
t = int(input())
for i in range(t):
	(s, n) = input().split()
	n = int(n)
	inc = 0
	lol = []
	ans = 0
	for j in range(len(s)):
		if s[j] == 'a':
			inc += 1
		else:
			inc -= 1
		lol.append(inc)
	if inc == 0:
		for j in range(len(s)):
			if lol[j] > 0:
				ans += n
	elif inc > 0:
		for j in range(len(s)):
			if lol[j] > 0:
				ans += n
			elif lol[j] == 0:
				ans += n - 1
			else:
				wasted = -lol[j] // inc + 1
				if wasted < n:
					ans += n - wasted
	else:
		for j in range(len(s)):
			if lol[j] > 0:
				safe = math.ceil(lol[j] / -inc)
				if safe <= n:
					ans += safe
				else:
					ans += n
	print(ans)


t = int(input())
while t > 0:
	(s, n) = input().split()
	n = int(n)
	x = 0
	w = []
	for i in range(0, len(s)):
		if s[i] == 'a':
			x += 1
		else:
			x -= 1
		w.append(x)
	ans = 0
	if x == 0:
		for i in range(0, len(s)):
			if w[i] > 0:
				ans += n
	elif x < 0:
		for i in range(0, len(s)):
			temp = 0
			if w[i] > 0:
				temp = int(w[i] / -x)
				if w[i] % -x != 0:
					temp += 1
			ans += min(temp, n)
	else:
		for i in range(0, len(s)):
			temp = 0
			if w[i] <= 0:
				temp = int(-w[i] / x) + 1
			ans += max(n - temp, 0)
	print(ans)
	t -= 1


import math
T = int(input())
for t in range(T):
	(s1, s2) = list(input().split())
	s = s1
	n = int(s2)
	c = 0
	cc = 0
	x = len(s)
	freq = [[0, 0] for i in range(len(s))]
	if s[0] == 'a':
		freq[0][0] = 1
	if s[0] == 'b':
		freq[0][1] = 1
	for i in range(1, len(s)):
		if s[i] == 'a':
			freq[i][0] = 1
		else:
			freq[i][1] = 1
		freq[i][0] += freq[i - 1][0]
		freq[i][1] += freq[i - 1][1]
	x = freq[len(s) - 1][0] - freq[len(s) - 1][1]
	for i in range(0, len(s)):
		d = x
		a = freq[i][0] - freq[i][1]
		if d > 0:
			if a > 0:
				c += n
			elif a < 0:
				h = 1 + math.ceil(abs(a) / d)
				if h <= n:
					if a + (h - 1) * d == 0:
						c += n - h
					else:
						c += n - (h - 1)
			elif a == 0:
				c += n - 1
		elif d < 0:
			if a > 0:
				h = 1 + math.ceil(a / abs(d))
				if h <= n:
					c += h - 1
				else:
					c += n
		elif d == 0:
			if a > 0:
				c += n
	print(c)


def function(s, n):
	prev = 0
	a = b = c = f = 0
	while n != 0:
		current = 0
		for i in range(len(s)):
			if s[i] == 'a':
				a += 1
			else:
				b += 1
			if a > b:
				current += 1
		if current == prev:
			f = 1
			break
		else:
			prev = current
			c += current
		n -= 1
	if f:
		return c + current * n
	else:
		return c
for _ in range(int(input())):
	(s, n) = map(str, input().split())
	n = int(n)
	result = function(s, n)
	print(result)


t = int(input())
for i in range(t):
	(s, n) = list(input().split())
	n = int(n)
	count = 0
	ano = 0
	bno = 0
	for j in s:
		if j == 'a':
			ano = ano + 1
		if j == 'b':
			bno = bno + 1
	if ano == bno:
		tempa = 0
		tempb = 0
		for y in s:
			if y == 'a':
				tempa = tempa + 1
			elif y == 'b':
				tempb = tempb + 1
			if tempa > tempb:
				count = count + 1
		print(count * n, end='\n')
	elif ano > bno:
		temp1 = ano - bno
		temp1 = 500 // temp1
		temp2 = min(temp1, n)
		tempa = 0
		tempb = 0
		for x in range(temp2):
			for y in s:
				if y == 'a':
					tempa = tempa + 1
				elif y == 'b':
					tempb = tempb + 1
				if tempa > tempb:
					count = count + 1
		if temp2 < n:
			print(count + (n - temp2) * len(s), end='\n')
		else:
			print(count, end='\n')
	else:
		temp1 = bno - ano
		temp1 = 500 // temp1
		temp2 = min(temp1, n)
		tempa = 0
		tempb = 0
		for x in range(temp2):
			for y in s:
				if y == 'a':
					tempa = tempa + 1
				elif y == 'b':
					tempb = tempb + 1
				if tempa > tempb:
					count = count + 1
		print(count, end='\n')


test_cases = int(input())
for i in range(test_cases):
	(string, n) = input().split(' ')
	n = int(n)
	temp = 0
	length = len(string)
	valid_prefixes = 0
	a_bef_b = []
	for s in string:
		if s == 'a':
			temp += 1
			a_bef_b.append(temp)
		else:
			temp -= 1
			a_bef_b.append(temp)
	act_diff = a_bef_b[-1]
	min_element = min(a_bef_b)
	max_element = max(a_bef_b)
	if act_diff > 0:
		times_loop = int(abs(min_element / act_diff)) + 1
		if times_loop <= n:
			for num in a_bef_b:
				if num <= 0:
					valid_prefixes += times_loop - int(abs(num / act_diff)) - 1
				else:
					valid_prefixes += times_loop
			valid_prefixes += (n - times_loop) * length
		else:
			for num in a_bef_b:
				if num <= 0:
					val = int(abs(num / act_diff))
					if n > val + 1:
						valid_prefixes += n - val - 1
				else:
					valid_prefixes += n
	elif act_diff == 0:
		times_loop = 1
		for num in a_bef_b:
			if num > 0:
				valid_prefixes += times_loop
		temp = valid_prefixes
		valid_prefixes += (n - times_loop) * temp
	else:
		times_loop = int(abs(max_element / act_diff)) + 1
		if times_loop < n:
			for num in a_bef_b:
				if num > 0:
					if num % abs(act_diff) == 0:
						valid_prefixes += int(abs(num / act_diff))
					else:
						valid_prefixes += int(abs(num / act_diff)) + 1
		else:
			for num in a_bef_b:
				if num > 0:
					val = int(abs(num / act_diff))
					if num % abs(act_diff) == 0:
						if val > n:
							valid_prefixes += n
						else:
							valid_prefixes += val
					elif val >= n:
						valid_prefixes += n
					else:
						valid_prefixes += val + 1
	print(valid_prefixes)


import numpy as np
T = int(input())
for _ in range(T):
	(s, n) = input().split()
	n = int(n)
	ms = len(s)
	vals = [0 for i in range(ms)]
	c = 0
	for i in range(ms):
		if s[i] == 'a':
			c += 1
		else:
			c -= 1
		vals[i] = c
	vals = np.array(vals)
	dv = vals[-1]
	if dv == 0:
		count = (vals > 0).sum() * n
	elif dv > 0:
		count = 0
		for i in range(n):
			dp = (vals > 0).sum()
			count += dp
			if dp == ms:
				break
			vals += dv
		if i < n:
			count += (n - i - 1) * ms
	else:
		count = 0
		for i in range(n):
			dp = (vals > 0).sum()
			count += dp
			if dp == 0:
				break
			vals += dv
	print(count)


t = int(input())
while t:
	t -= 1
	(s, n) = input().split()
	n = int(n)
	x = int(s.count('a') - s.count('b'))
	noofbees = s.count('b')
	noofas = s.count('a')
	if x == 0:
		abcount = 0
		count = 0
		for c in s:
			if c == 'a':
				abcount += 1
			else:
				abcount -= 1
			if abcount > 0:
				count += 1
		print(count * n)
	elif x > 0:
		count = 0
		abcount = 0
		strcount = 1
		extra = 0
		while abcount <= noofbees and strcount <= n:
			for c in s:
				if c == 'a':
					abcount += 1
				else:
					abcount -= 1
				if abcount > 0:
					count += 1
			strcount += 1
		if strcount <= n:
			extra = (n - strcount + 1) * len(s)
		print(count + extra)
	else:
		count = 0
		abcount = 0
		strcount = 1
		while abcount + noofas >= 0 and strcount <= n:
			for c in s:
				if c == 'a':
					abcount += 1
				else:
					abcount -= 1
				if abcount > 0:
					count += 1
			strcount += 1
		print(count)


for i in range(int(input())):
	(s, n) = map(str, input().split())
	n = int(n)
	(k, na, nb, c, m, t) = (0, 0, 0, 0, 0, 1)
	for i in range(len(s)):
		if s[i] == 'a':
			na += 1
		else:
			nb += 1
		if na > nb:
			k += 1
	c += k
	if n == 1:
		print(c)
	else:
		while k != m and t < n:
			k = m
			m = 0
			for i in range(len(s)):
				if s[i] == 'a':
					na += 1
				else:
					nb += 1
				if na > nb:
					m += 1
			c += m
			t += 1
		c += (n - t) * m
		print(c)


for _ in range(int(input())):
	(data, n) = input().split()
	n = int(n)
	data = list(data)
	a_count = [0] * (len(data) + 1)
	b_count = [0] * (len(data) + 1)
	diff = [0] * (len(data) + 1)
	ans = 0
	for i in range(len(data)):
		if data[i] == 'a':
			a_count[i + 1] = a_count[i] + 1
		else:
			a_count[i + 1] = a_count[i]
		if data[i] == 'b':
			b_count[i + 1] = b_count[i] + 1
		else:
			b_count[i + 1] = b_count[i]
		diff[i + 1] = a_count[i + 1] - b_count[i + 1]
		if diff[i + 1] > 0:
			ans += 1
	if diff[-1] == 0:
		print(ans * n)
		continue
	if diff[-1] < 0:
		ans_for_1 = 0
		for x in diff:
			if x > 0:
				ans_for_1 += 1
		n_index = 1
		temp_ans = ans_for_1
		main_ans = ans_for_1
		z = diff[-1]
		while n_index < n and temp_ans != 0:
			temp_ans = 0
			for each in range(1, len(diff)):
				diff[each] += z
				if diff[each] > 0:
					temp_ans += 1
			main_ans += temp_ans
			n_index += 1
		print(main_ans)
		continue
	if diff[-1] > 0:
		ans_for_1 = 0
		for x in diff:
			if x > 0:
				ans_for_1 += 1
		n_index = 1
		temp_ans = ans_for_1
		main_ans = ans_for_1
		z = diff[-1]
		while n_index < n and temp_ans != len(data):
			temp_ans = 0
			for each in range(1, len(diff)):
				diff[each] += z
				if diff[each] > 0:
					temp_ans += 1
			main_ans += temp_ans
			n_index += 1
		if n == n_index:
			print(main_ans)
		else:
			print(main_ans + len(data) * (n - n_index))


t = int(input())
for i in range(t):
	(s, n) = input().split(' ')
	n = int(n)
	length = len(s)
	a = 0
	b = 0
	satisfied = 0
	notSatisfied = 0
	for j in range(0, length):
		if s[j] == 'a':
			a += 1
		else:
			b += 1
		if a > b:
			satisfied += 1
	if a > b:
		ans = satisfied
		n -= 1
		while n != 0 and satisfied != length:
			n -= 1
			satisfied = 0
			notSatisfied = 0
			for j in range(0, length):
				if s[j] == 'a':
					a += 1
				else:
					b += 1
				if a > b:
					satisfied += 1
			ans += satisfied
		ans += n * length
		print(ans)
	elif a < b:
		ans = satisfied
		n -= 1
		while n != 0 and satisfied != 0:
			n -= 1
			satisfied = 0
			for j in range(0, length):
				if s[j] == 'a':
					a += 1
				else:
					b += 1
				if a > b:
					satisfied += 1
			ans += satisfied
		print(ans)
	else:
		ans = satisfied * n
		print(ans)


T = int(input())
for t in range(0, T):
	st = input()
	(s, e) = st.split()
	n = int(e)
	l1 = len(s)
	n = int(e)
	d1 = 0
	d2 = 0
	d3 = 0
	a = [0] * l1
	for j in range(0, l1):
		if s[j] == 'a':
			a[j] = 1
			d1 += 1
		else:
			a[j] = -1
			d2 += 1
	for j in range(1, l1):
		a[j] = a[j] + a[j - 1]
		if a[j] > 0:
			d3 += 1
	if a[0] > 0:
		d3 += 1
	count = 0
	if d2 == d1:
		count = d3 * n
		print(count)
	elif d1 < d2:
		for k in range(0, l1):
			if a[k] > 0:
				if a[k] < n:
					if a[k] % (d2 - d1) == 0:
						count += a[k] // (d2 - d1)
					else:
						count += a[k] // (d2 - d1) + 1
				elif a[k] % (d2 - d1) == 0:
					if a[k] // (d2 - d1) < n:
						count += a[k] // (d2 - d1)
					else:
						count += n
				elif a[k] // (d2 - d1) + 1 > n:
					count += n
				else:
					count += a[k] // (d2 - d1) + 1
		print(int(count))
	else:
		c1 = 0
		count = n * l1
		for k in range(0, l1):
			if a[k] < 1:
				c1 = 1 - a[k]
				if c1 < n:
					if c1 % (d1 - d2) == 0:
						count -= c1 // (d1 - d2)
					else:
						count -= c1 // (d1 - d2) + 1
				elif c1 % (d1 - d2) == 0:
					if c1 // (d1 - d2) < n:
						count -= c1 // (d1 - d2)
					else:
						count -= n
				elif c1 // (d1 - d2) < n:
					count -= c1 // (d1 - d2) + 1
				else:
					count -= n
		print(int(count))


T = int(input())
for _ in range(T):
	(s, r) = input().split()
	r = int(r)
	total = 0
	count_prev = 0
	count_curr = 0
	count_a = 0
	count_b = 0
	count = 0
	for i in range(len(s)):
		if s[i] == 'a':
			count_a += 1
		else:
			count_b += 1
		if count_a > count_b:
			count += 1
	if count == 0:
		print(0)
	else:
		count_prev = count
		total = count
		n = 1
		while n != r:
			count = 0
			for i in range(len(s)):
				if s[i] == 'a':
					count_a += 1
				else:
					count_b += 1
				if count_a > count_b:
					count += 1
			count_curr = count
			total += count_curr
			n += 1
			if count_curr == count_prev:
				break
			count_prev = count_curr
		total += (r - n) * count_prev
		print(total)


from math import ceil
for _ in range(int(input())):
	(s, n) = input().split()
	n = int(n)
	dp = [1 if c == 'a' else -1 for c in s]
	for i in range(1, len(s)):
		dp[i] += dp[i - 1]
	diff = dp[-1]
	res = 0
	for val in dp:
		if diff > 0:
			start = int(ceil(max(0, 1 - val) / diff))
			res += max(n - start, 0)
		elif diff < 0:
			end = int(ceil(max(0, val) / -diff))
			res += min(n, end)
		elif val > 0:
			res += n
	print(res)


for _ in range(int(input())):
	(s, m) = [x for x in input().split()]
	m = int(m)
	(ta, tb, h) = (0, 0, 0)
	for i in s:
		if i == 'a':
			ta += 1
		else:
			tb += 1
		if ta > tb:
			h += 1
	if ta == tb:
		print(h * m)
		continue
	m -= 1
	cnt = h
	while m:
		h = 0
		for i in s:
			if i == 'a':
				ta += 1
			else:
				tb += 1
			if ta > tb:
				h += 1
		m -= 1
		cnt += h
		if h >= len(s) or h == 0:
			break
	if h:
		cnt += m * len(s)
	print(cnt)


def prefixcount(string):
	(counta, prefixcount) = (0, 0)
	for x in string:
		if x == 'a':
			counta += 1
			if counta > 0:
				prefixcount += 1
		else:
			counta -= 1
			if counta > 0:
				prefixcount += 1
	return prefixcount
for t in range(int(input())):
	(text, period) = input().split()
	p = int(period)
	numA = text.count('a')
	numB = len(text) - numA
	if numA == numB:
		print(prefixcount(text) * p)
	elif numA > numB:
		tsjop = 0
		check = numB // (numA - numB) + 1
		if check > p:
			check = p
		else:
			tsjop = 1
		prefix = prefixcount(text * check)
		if tsjop:
			print(prefix + len(text) * (p - check))
		else:
			print(prefix)
	elif numB > numA:
		check = numA // (numB - numA) + 1
		if check > p:
			check = p
		print(prefixcount(text * check))


from math import *
t = int(input())
for i in range(t):
	(s, n) = input().split()
	n = int(n)
	y = 10000
	sumx = 0
	total = 0
	a = []
	for j in range(len(s)):
		if s[j] == 'a':
			sumx += 1
		else:
			sumx -= 1
		if sumx > 0:
			total += 1
		a.append(sumx)
	y = min(a)
	if sumx < 0 and y < 0:
		for j in range(len(s)):
			if a[j] > 0:
				total += min(ceil(a[j] / abs(sumx)) - 1, n - 1)
	elif sumx == 0:
		for j in range(len(s)):
			if a[j] > 0:
				total += n - 1
	elif sumx > 0 and y < 0:
		for j in range(len(s)):
			if a[j] > 0:
				total += n - 1
			else:
				x = floor(abs(a[j]) / sumx)
				if n - 1 - x >= 0:
					total += n - 1 - x
	else:
		total += (n - 1) * len(s)
	print(total)


def countSubStrings(s):
	a = 0
	b = 0
	count = 0
	for i in range(len(s)):
		if s[i] == 'a':
			a += 1
		elif s[i] == 'b':
			b += 1
		if a > b:
			count += 1
	return count

def countSubStringAfter(s, ta, tb, prev):
	a = ta
	b = tb
	count = 0
	for i in range(len(s)):
		if s[i] == 'a':
			a += 1
		elif s[i] == 'b':
			b += 1
		if a > b:
			count += 1
	return count + prev
T = int(input())
for i in range(T):
	line = input()
	s = line.split()[0]
	n = int(line.split()[1])
	noOfA = s.count('a')
	noOfB = s.count('b')
	ans = countSubStrings(s)
	x = s
	ans2 = countSubStrings(x + s)
	ta = noOfA
	tb = noOfB
	if noOfA == noOfB:
		ans *= n
	elif noOfA > noOfB:
		i = 1
		while ans2 - ans < len(s) and i < n:
			i += 1
			x += s
			ans = ans2
			ta += noOfA
			tb += noOfB
			ans2 = countSubStringAfter(s, ta, tb, ans)
		if i < n:
			ans += (n - i) * len(s)
	elif noOfB > noOfA:
		i = 1
		while ans2 - ans > 0 and i < n:
			i += 1
			x += s
			ans = ans2
			ta += noOfA
			tb += noOfB
			ans2 = countSubStringAfter(s, ta, tb, ans)
	print(ans)


from math import ceil
t = int(input())
while t > 0:
	st = input().split()
	n = int(st[-1])
	times = 0
	if n == 1:
		a = 0
		b = 0
		counter = 0
		for i in st[0]:
			if i == 'a':
				a += 1
			if i == 'b':
				b += 1
			if a > b:
				counter += 1
			times += 1
		print(counter)
	else:
		length = len(st[0])
		count_1 = [-1] * length
		count_2 = [-1] * length
		ans = 0
		for i in range(length):
			times += 1
			if i == 0:
				if st[0][i] == 'a':
					count_1[i] = 1
				else:
					count_1[i] = -1
			elif st[0][i] == 'a':
				count_1[i] = count_1[i - 1] + 1
			else:
				count_1[i] = count_1[i - 1] - 1
		idx = 0
		for i in range(length - 1, -1, -1):
			if idx == 0:
				if st[0][idx] == 'a':
					count_2[idx] = count_1[i] + 1
				if st[0][idx] == 'b':
					count_2[idx] = count_1[i] - 1
			elif st[0][idx] == 'a':
				count_2[idx] = count_2[idx - 1] + 1
			else:
				count_2[idx] = count_2[idx - 1] - 1
			idx += 1
		if count_1[0] == count_2[0]:
			for i in count_1:
				if i > 0:
					ans += 1
				times += 1
			print(ans * n)
		elif count_1[0] < count_2[0]:
			diff = [-1] * length
			for i in range(length):
				diff[i] = abs(count_2[i] - count_1[i])
				times += 1
			for i in count_1:
				if i > 0:
					ans += 1
				times += 1
			for i in count_2:
				if i > 0:
					ans += 1
				times += 1
			exc = 0
			for i in range(length):
				if count_2[i] >= 0:
					ans += n - 2
				else:
					rem = n - 2
					if abs(count_2[i]) < diff[i]:
						ans += rem
					elif abs(count_2[i]) == diff[i]:
						ans += max(rem - 1, 0)
					else:
						ans += max(rem - abs(count_2[i]) // diff[i], 0)
				times += 1
			print(ans)
		else:
			diff = [-1] * length
			for i in range(length):
				diff[i] = abs(count_2[i] - count_1[i])
				times += 1
			for i in count_1:
				if i > 0:
					ans += 1
				times += 1
			for i in count_2:
				if i > 0:
					ans += 1
				times += 1
			rem = n - 2
			for i in range(length):
				times += 1
				if count_2[i] > 0:
					if count_2[i] % diff[i] == 0:
						ans += min(count_2[i] // diff[i] - 1, rem)
					else:
						ans += count_2[i] // diff[i]
			print(ans)
	t -= 1


def numg0(ls):
	count = 0
	for i in ls:
		if i > 0:
			count += 1
	return count

def allg0(ls, limiter=float('inf')):
	count = 0
	counter = 0
	numg = numg0(ls)
	numg_in = numg
	the_last = ls[-1]
	while numg != len(ls) and numg != 0 and (counter != limiter):
		count += numg
		counter += 1
		ls = [x + the_last for x in ls]
		numg = numg0(ls)
		if numg == numg_in:
			break
	if numg == 0:
		charic = 0
	elif numg == len(ls):
		charic = len(ls)
	else:
		charic = numg
	return (count, counter, charic)
T = int(input())
for kappa in range(T):
	(s, n) = list(input().split())
	n = int(n)
	if s[0] == 'a':
		ls = [1]
	else:
		ls = [-1]
	for i in s[1:]:
		if i == 'a':
			ls.append(ls[-1] + 1)
		else:
			ls.append(ls[-1] - 1)
	allg = allg0(ls)
	count = allg[0]
	counter = allg[1]
	charic = allg[2]
	if n > counter:
		print((n - counter) * charic + count)
	else:
		allg = allg0(ls, n)
		print(allg[0])


def solve(s, n):
	orig = len(s)
	(a, b) = (s.count('a'), s.count('b'))
	if n == 1:
		(co, c1, c2) = (0, 0, 0)
		for i in range(orig):
			if s[i] == 'a':
				c1 = c1 + 1
			else:
				c2 = c2 + 1
			if c1 > c2:
				co = co + 1
		print(co)
	else:
		if a > b:
			(co, c1, c2) = (0, 0, 0)
			x = min(b // (a - b) + 1, n)
			k = s * x
			for i in range(len(k)):
				if k[i] == 'a':
					c1 = c1 + 1
				else:
					c2 = c2 + 1
				if c1 > c2:
					co = co + 1
			co = co + orig * (n - x)
		elif b > a:
			(co, c1, c2) = (0, 0, 0)
			x = min(a // (b - a) + 1, n)
			k = s * x
			for i in range(len(k)):
				if k[i] == 'a':
					c1 = c1 + 1
				else:
					c2 = c2 + 1
				if c1 > c2:
					co = co + 1
		else:
			(co, c1, c2) = (0, 0, 0)
			for i in range(orig):
				if s[i] == 'a':
					c1 = c1 + 1
				else:
					c2 = c2 + 1
				if c1 > c2:
					co = co + 1
			co = co * n
		print(co)
for inm in range(int(input())):
	(a, b) = map(str, input().split())
	solve(a, int(b))