#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define pii pair<int,int>
#define fs first
#define sc second
#define pb push_back
#define epb emplace_back
#define endl
#define SZ(X) (int)((X).size())
template<typename T>T mabs(T x){return x>=0?x:-x;}
const int N=1.1e6,mod=1e9+7;
char s[N],t[N];
LL pre[N];
int ff(int c){
	if(c==0)return 0;
	if(c==1)return 1;
	if(c==3)return 2;
	if(c==2)return 3;
	cerr<<"??"<<c<<"\n";
	abort();
}
void init(){
	pre[0]=1;
	for(int i=1;i<=1e6;i++)
		pre[i]=pre[i-1]*4%mod;
	
	//pre[0]=5;	
	for(int i=1;i<=1e6;i++)
		pre[i]+=pre[i-1],pre[i]%=mod;
}
void work(){
	int k;
	scanf("%s%s%d",s,t,&k);
	reverse(s,s+strlen(s));
	reverse(t,t+strlen(t));
	int l=max(strlen(s),strlen(t));
	for(int i=0;i<l;i++){
		if(s[i]>0)s[i]-='0';
		if(t[i]>0)t[i]-='0';
		s[i]^=t[i];
		//cerr<<(int)s[i]<<"%";
	}
	LL ans=0;
	for(int i=0;i<l;i+=2){
		int c=s[i]+s[i+1]*2;
		ans+=ff(c)*pre[i/2];
		//cerr<<i<<"@"<<c<<"#"<<ans<<"\n";
		ans%=mod;
	}
	//cout<<ans<<"\n";
	for(int i=0;i<l;i++)s[i]=t[i]=0;
	LL cnt=0;
	for(int i=0;i<l;i+=2){
		int c=s[i]+s[i+1]*2;
		if(c!=0)goto E;
		cnt++;
	}
	cnt=1e18+1;
	E:
	ans+=pre[k-1]-1;
	if(k-1<cnt)cout<<ans<<"\n";
	else cout<<"-1\n";
}
int main(){
	int t;
	init();
	scanf("%d",&t);
	while(t--)work();
	return 0;
}