#include<bits/stdc++.h>
#pragma optimize(2)
#define int long long
using namespace std;
int read()
{
	int x = 0, f = 1;
	char c = getchar();
	while(c != EOF and !isdigit(c))
	{
		if(c == '-')f = -1;
		c = getchar();
	}
	while(isdigit(c))
	{
		x = x * 10 + c - '0';
		c = getchar();
	}
	return x * f;
}
int n, m, k;
char s[1000010], p[1000010];
int mod = 1e9+7;
int M[4] = {0, 1, 3, 2};
int c[1000010], a[1000010], b[1000010];
int pows[1000010];
signed main()
{
	pows[0] = 1;
	for(int i = 1;i <= 1e6;i ++)pows[i] = pows[i - 1] * 4 % mod;
	for(int i = 1;i <= 1e6;i ++)pows[i] = (pows[i] + pows[i - 1]) % mod;
	int T = read();
	while(T --)
	{
		
		cin>>s+1;
		cin>>p+1;
		
		k = read();
		n = strlen(s + 1);
		m = strlen(p + 1);
		int len = max(n, m) + (max(n, m) & 1ll), maxn = 0;
		for(int i = 1;i <= len;i ++)
		{
			if(i <= n)a[i] = s[n - i + 1] - '0';
			else a[i] = 0;
			if(i <= m)b[i] = p[m - i + 1] - '0';
			else b[i] = 0;
		}
		len /= 2;
		for(int i = 1;i <= len;i ++)
		{
			int fi = a[(i<<1) - 1] ^ b[(i<<1) - 1];
			int se = a[(i<<1)] ^ b[(i<<1)];
			int x = fi + se * 2;
			//cout<<i<<' '<<x<<endl;
			if(x != 0)maxn = i;
			c[i] = M[x];
		}
		if(! maxn)
		{
			cout<<(pows[k - 1] - 1 + mod) % mod<<'\n';
		}
		else if(k > maxn)
		{
			cout<<-1<<'\n';
		}
		else
		{
			c[k - 1] = 4;
			int ans = 0;
			for(int i = 1;i <= len;i ++)
			{
				//cout<<c[i]<<' '<<pows[i]<<endl;
				ans = (ans + c[i] * pows[i - 1] % mod) % mod;
			}
			cout<<ans<<'\n';
		}
		for(int i = 1;i <= len;i ++)a[i] = b[i] = '0';
	}
	return 0;
}