#include <bits/stdc++.h>
 
using namespace std;
 
const int MaxN = (int)1e5 + 10;
const int INF = (int)1e9;
const int MOD = (int)1e9 + 7;

const int SHIFT = 2018 / 2;

int cnt[2 * SHIFT];
 
int main() {
//	freopen("input.txt", "r", stdin);
	ios::sync_with_stdio(false); cin.tie(NULL);
	int t;
	cin >> t;
	assert (1 <= t && t <= 100);
	while (t --> 0) {
		string s;
		cin >> s;
		assert (1 <= s.length() && s.length() <= 1000);
		int n, bal = 0;
		cin >> n;
		assert (1 <= n && n <= 1e9);
		long long ans = 0;
		memset(cnt, 0, sizeof(cnt));
		for (int i = 0; i < (int)s.length(); ++i) {
			assert (s[i] == 'a' || s[i] == 'b');
			bal += s[i] == 'a' ? 1 : -1;
			if (bal > 0) {
				ans += 1;
			}
			cnt[SHIFT + bal] += 1;
		}
		for (int i = 1; i < 2 * SHIFT; ++i) {
			cnt[i] += cnt[i - 1];
		}
		if (bal == 0) {
			ans *= n;
		} else if (bal > 0) {
			long long cur = bal;
			int last = 1;
			for (int i = 2; i <= n && cur <= (int)s.length(); ++i) {
				//cur + x > 0
				//x > -cur
				ans += cnt[2 * SHIFT - 1] - cnt[SHIFT - cur];
				last = i;
				cur += bal;
			}
			ans += 1LL * (n - last) * (int)s.length();
		} else {
			long long cur = bal;
			for (int i = 2; i <= n && cur >= -(int)s.length(); ++i) {
				ans += cnt[2 * SHIFT - 1] - cnt[SHIFT - cur];
				cur += bal;
			}
		}
		cout << ans << "\n";
	}
	return 0;
}