/*
 *
 ********************************************************************************************
 * AUTHOR : Vijju123                                                                        *
 * Language: C++14                                                                          *
 * Purpose: -                                                                               *
 * IDE used: Codechef IDE.                                                                  *
 ********************************************************************************************
 *
 Comments will be included in practice problems if it helps ^^
 */



#include <iostream>
#include<bits/stdc++.h>
using namespace std;

int main() {
	// your code goes here
	#ifdef JUDGE
    freopen("input.txt", "rt", stdin);
    freopen("output.txt", "wt", stdout);
    #endif
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	cout.tie(NULL);
	int t;
	cin>>t;
	while(t--)
	{
	    int n;
	    string s;
	    cin>>s>>n;
	    int a=0,b=0,goodPrefix=0;
	    for(auto i:s)
	    {
	        if(i=='a')a++;
	        else b++;
	        if(a>b)goodPrefix++;
	    }
	    if(n==1)cout<<goodPrefix<<endl;
	    else if(a==b)
	        cout<<1LL*n*goodPrefix<<endl;//Each appendation will give same number of good prefixes
	    else {
	        //We will simulate.
	        //Note that if a>b or a<b , then there must be AT LEAST a minimum increment/decrement of 1 
	        //after every appendation. Eg- bbbbaaaa n=1 has answer 1. Append it to itself, then answer
	        //we get "2 new" prefixes to give final answer of 3. Since length of string is k, 
	        //the maximum increment possible is k.
	        
	        //For decrement part, take example aaabbbb. n=1 answer is 5. After apppending, we get only "3 new"
	        //prefixes to give final answer of 8. The minimum contribution of an appending string is 0.
	        
	        //We see that at each appendation, the number of "new prefixes" increases/decreases by 1.
	        //==> Atmost 1000 iterations worth simulation needed. If new prefixes decrement, then after 
	        //at most 1000 iterations new appendations will have 0 contribution to answer- and if 
	        //new prefixes increment, after 1000 iterations their value will be 1000 (=length of string)
	        //We can calculate both these cases by formula
	        
	        string t="";
	        int incr=-1,i=0;
	        long long ans=0,prevAns=0;
	        int k=s.length(),tempN=n;
	        a=0;
	        b=0;
	        while(tempN-- and incr!=k and incr!=0)//If change !=length of string and !=0 
	        {
	            t+=s;
	            for(;i<t.length();i++)
	            {
	                if(t[i]=='a')++a;
	                else ++b;
	                if(a>b)
	                {
	                    ++ans;
	                }
	            }
	            incr=ans-prevAns;//change in final answer.
	            prevAns=ans;
	        }
	        incr=max(incr,0);//In case incr goes negative
	        ans+=1LL*(tempN+1)*incr;//Why tempN+1? Focus on "tempN--". when tempN becomes 0, it goes to "0--= -1"
	        cout<<ans<<endl;
	    }
	    
	}
	
	return 0;
}