#include <bits/stdc++.h>
using namespace std;
const int mod=1000000007;
const int inv2=500000004;
const int inv3=333333336;
string s,t;
bitset<1000000>m;
int tot;
int step()
{
	int id=m._Find_first();
	return id/2+1;
}
long long power(long long n,int p)
{
    long long ans=1;
    while(p)
    {
        if(p&1)
        ans=ans*n%mod;
        p>>=1;
        n=n*n%mod;
    }
    return ans;
}
/*
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)*inv3%mod;
}
void shuchu()
{
	bitset<10>w=m.to_ulong();
	cout<<w<<endl;
}
int ask(int len,int k)
{
//	shuchu(m);
//	cout<<len<<" "<<k<<endl;
	if(len<m._Find_first()+1)
	{
		return calc(k); 
	}
	if(!m[len-1])
	{
		return ask(len-1,k);
	}
	if(len==m._Find_first()+1&&step()==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*inv2%mod*3%mod+1;
			}
			else
			{
				return calc((len+1)/2)+1;
			}
		}
//		cout<<len-2*(step()-k+1)-(len%2==0)<<" "<<step()<<" "<<len<<" "<<k<<endl;
		m.set(len-2*(step()-k+1)-(len%2==0),1);
		return ask(len,k-1)+1;
	}
	else
	{
		if(len%2==0)
		{
			tot++;
			if(m[len-1-1])
			{
				m[len-1-1]=0;
	//			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;
			}
			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)*inv2%mod*3%mod)%mod;
			}
		}
//		cout<<calc((len-1)/2+1)*power(2,(len-1)%2)<<endl;
		tot++;
//		cout<<"tot++"<<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);
//	freopen("M.in","r",stdin);
	int T;
	cin>>T;
	while(T--)
	{
		int k;
		cin>>s>>t>>k;
		reverse(s.begin(),s.end());
		reverse(t.begin(),t.end());
		for(int i=max(s.size(),t.size())-1;i>=0;i--)
		{
			if(i<s.size())
			{
		//		cout<<i<<"s!!!s"<<s[i]-'0'<<endl;
				m[i]=m[i]^(s[i]-'0');
		//		cout<<m[i]<<endl;
			}
			if(i<t.size())
			{
		//		cout<<i<<"t!!!t"<<t[i]-'0'<<" "<<t[i]<<endl;
				m[i]=m[i]^(t[i]-'0');
		//		cout<<m[i]<<endl;
			}
		}
	//	shuchu();
	//	m=bitset<1000000>(s)^bitset<1000000>(t); 
		if(m.none())
		{
			cout<<calc(k)-1<<"\n";
		}
		else if(k>step())
		{
			cout<<-1<<"\n";
		}
		else
		{
			cout<<ask(max(s.size(),t.size()),k)-1<<"\n";
		}
		cout<<tot<<"\n";
	//	m.reset();
		
		for(int i=max(s.size(),t.size())-1;i>=0;i--)
		{
			m[i]=0;
		}
		
	}
	cout<<(double)clock()/1000<<endl;
	return 0;
}
/*
1
0 11100 2
*/