const int MAXB=15,MAXN=20,mod=1e9+7;
int a[MAXN],b[MAXN],c[MAXN],nxt[1<<MAXB][4],dp[2][1<<MAXB],ans[MAXN];
char s[MAXN];
void decode(int p,int n){
	_rep(i,1,n){
		b[i]=p&1;
		b[i]+=b[i-1];
		p>>=1;
	}
}
int encode(int n){
	int p=0;
	for(int i=n;i;i--){
		c[i]-=c[i-1];
		p<<=1;
		p+=c[i];
	}
	return p;
}
void add(int &a,int b){
	a+=b;
	a%=mod;
}
void solve(){
	scanf("%s",s+1);
	int n=strlen(s+1),m=read_int();
	_rep(i,1,n){
		if(s[i]=='A')
		a[i]=0;
		else if(s[i]=='G')
		a[i]=1;
		else if(s[i]=='T')
		a[i]=2;
		else
		a[i]=3;
	}
	int S=1<<n;
	_for(i,0,S){
		decode(i,n);
		_for(j,0,4){
			_rep(k,1,n){
				if(a[k]==j)
				c[k]=b[k-1]+1;
				else
				c[k]=max(c[k-1],b[k]);
			}
			nxt[i][j]=encode(n);
		}
	}
	int pos=0;
	mem(dp[pos],0);
	dp[pos][0]=1;
	_for(k,0,m){
		pos=!pos;
		mem(dp[pos],0);
		_for(i,0,S){
			_for(j,0,4)
			add(dp[pos][nxt[i][j]],dp[!pos][i]);
		}
	}
	mem(ans,0);
	_for(i,0,S){
		decode(i,n);
		add(ans[b[n]],dp[pos][i]);
	}
	_rep(i,0,n)
	enter(ans[i]);
}
int main()
{
	int T=read_int();
	while(T--)
	solve();
	return 0;
}