#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define mk make_pair
#define lowbit(x) (x&(-x))
#define pb emplace_back
#define pr pair<int,int>
#define let const auto
#define all(A) A.begin(),A.end()
void chkmin(int &x,int y){x=min(x,y);}
void chkmax(int &x,int y){x=max(x,y);}
const int N=1e6+5,mod=1e9+7;
int read(){
	int x=0,f=1; char c=getchar();
	while(('0'>c||c>'9')&&c!='-') c=getchar();
	if(c=='-') f=0,c=getchar();
	while('0'<=c&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return f?x:-x;
}
char s[N],t[N];
int a[N],pow5[N],mp[5];
void solve(){
	int k;
	scanf("%s%s%d",s+1,t+1,&k);
	int n=strlen(s+1),m=strlen(t+1);
	for(int i=0; i<n; i++) a[i]^=s[n-i]-'0';
	for(int i=0; i<m; i++) a[i]^=t[m-i]-'0';
	n=max(n,m)+1; n>>=1;
	auto chk = [&](){
		for(int i=0; i<n*2; i++) if(a[i]) return;
		n=60;
	};
	chk();
	int cur=1,cnt=0,ans=0;
	for(int i=0; i<n; i++) 
		if(a[i*2]==0&&a[i*2+1]==0) cur=min(k,cur*2),cnt++;
		else break;
	if(cur<k){
		for(int i=0; i<=n; i++) a[i*2]=a[i*2+1]=0;
		return puts("-1"),void();
	}
	k--;
	for(int i=n-1; ~i; i--){
		if(a[i*2]==0&&a[i*2+1]==0){
			cnt--; int t=0;
			if(cnt<=30&&((k>>cnt)&1)) t=4;
			ans=(ans+1ll*t*pow5[i])%mod;
		}
		else ans=(ans+1ll*mp[a[i*2]+2ll*a[i*2+1]]*pow5[i])%mod;
	}
	printf("%d\n",ans);
	for(int i=0; i<=n; i++) a[i*2]=a[i*2+1]=0;
}
int main(){
	mp[1]=1,mp[3]=2,mp[2]=3;
	for(int i=pow5[0]=1; i<=1e6; i++) pow5[i]=5ll*pow5[i-1]%mod;
	int T=read();
	while(T--) solve();
	return 0;
}