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

#define PB emplace_back
#define int long long
#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
#define per(i, a, b) for(int i = (a); i >= (b); --i)
#define siz(a) ((int) a.size())

const long long mod=1e9+7;
int d[1000005],T,an;

char s1[2000001],s2[2000001];
long long a,b,c,v1[2000001],v2[2000001],v[2000001];
signed main() {
	freopen(".in", "r", stdin);
	// freopen(".out", "w", stdout);
//	ios::sync_with_stdio(0);
//	cin.tie(0), cout.tie(0);
	scanf("%lld",&T);
	for(int i=1;i<=1000000;i++) d[i]=(d[i-1]*4+4)%mod;
	for(int ii=1;ii<=T;ii++)
	{
		an=0;
		scanf("%s%s",s1+1,s2+1);
		a=strlen(s1+1),b=strlen(s2+1);
		scanf("%lld",&c);
		long long hh=max(a,b);
		if(hh%2==1) ++hh;
		for(int i=1;i<=hh-a;i++) v1[i]=0;
		for(int i=hh-a+1;i<=hh;i++) v1[i]=s1[i-(hh-a)]-'0';
		for(int i=1;i<=hh-b;i++) v2[i]=0;
		for(int i=hh-b+1;i<=hh;i++) v2[i]=s2[i-(hh-b)]-'0';
		for(int i=1;i<=hh;i++) v[i]=(v1[i]^v2[i]);
		long long tt=hh/2;
		for(int i=hh;i>=1;i-=2)
		{
			if(v[i]||v[i-1])
			{
				tt=(hh-i+2)/2-1;
				break;
			}
		}
		if(tt!=hh/2&&c>tt+1)
		{
			printf("-1\n");
			continue;
		}
		for(int i=1;i<=hh/2;i++) swap(v[i],v[hh-i+1]);
		for(int i=hh;i>=1;i-=2)
		{
			long long gg=0;
			if(v[i]==0&&v[i-1]==0) gg=0;
			else if(v[i]==0&&v[i-1]==1) gg=1;
			else if(v[i]==1&&v[i-1]==1) gg=2;
			else gg=3;
			an+=((d[i/2-1]+1)*gg),an%=mod;
		}
		an+=d[c-1],an%=mod;
		printf("%lld\n",(an%mod+mod)%mod);
	}
	return 0;
}