#include <bits/stdc++.h>
using namespace std;
const int mod=1000000007;
string s,t;
bitset<1000000>m,tmp;
int step(bitset<1000000>x)
{
	int id=x._Find_first();
	return id/2+1;
}
long long power(int n,int p)
{
	if(p==0)
	{
		return 1;
	}
	long long tmp=power(n,p/2);
	if(p%2==1)
	{
		return tmp*tmp%mod*n%mod;
	}
	return tmp*tmp%mod;
}
int calc(int k)
{
	return (power(4,k)-1)*power(3,1000000005)%mod;
}
void shuchu(bitset<1000000>x)
{
	bitset<10>w=x.to_ulong();
	cout<<w<<endl;
}
int ask(int len,int k)
{
//	shuchu(m);
//	cout<<len<<" "<<k<<endl;
	if(len<m._Find_first()+1)
	{
		return 1; 
	}
	if(!m[len-1])
	{
		return ask(len-1,k);
	}
	if(len==m._Find_first()+1&&step(m)==k)
	{
		return (calc(len/2+1)*power(2,len%2)-(len%2==0))%mod;
	}
	else if(len==m._Find_first()+1)
	{
		if(k==1)
		{
			if(len%2==0)
			{
				return (calc((len-1)/2+1)*power(2,(len-1)%2)-((len-1)%2==0))%mod*power(2,1000000005)%mod*3%mod+1;
			}
			else
			{
				return calc((len+1)/2)+1;
			}
		}
		tmp=m;
	//	cout<<len-2*(step(m)-k+1)-(len%2==0)<<" "<<step(m)<<" "<<len<<" "<<k<<endl;
		tmp.set(len-2*(step(m)-k+1)-(len%2==0),1);
		m=tmp;
		return ask(len,k-1)+1;
	}
	else
	{
		if(len%2==0)
		{
			if(m[len-1-1])
			{
				tmp.reset();
				tmp.set(len-1-1,1);
				m=m^tmp;
				return (ask(len-1,k)+calc((len-1)/2+1)*power(2,(len-1)%2))%mod;
			}
			else
			{
		//		cout<<calc((len-1)/2+1)*power(2,(len-1)%2)*power(2,1000000005)%mod*3%mod<<endl;
				return (ask(len-1,k)+calc((len-1)/2+1)*power(2,(len-1)%2)*power(2,1000000005)%mod*3%mod)%mod;
			}
		}
	//	cout<<calc((len-1)/2+1)*power(2,(len-1)%2)<<endl;
		return (ask(len-1,k)+calc((len-1)/2+1)*power(2,(len-1)%2))%mod;
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T;
	cin>>T;
	while(T--)
	{
		int k;
		cin>>s>>t>>k;
		m=bitset<1000000>(s)^bitset<1000000>(t); 
		if(m.none())
		{
			cout<<calc(k)-1<<"\n";
		}
		else if(k>step(m))
		{
			cout<<-1<<"\n";
		}
		else
		{
			cout<<ask(max(s.size(),t.size()),k)-1<<"\n";
		}
	}
	return 0;
}