#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<string,ll> var;
int t;
const ll mod=1e9+9; 
string s;
ll k;
map<var,ll> f; 
namespace QiFeng233{
    ll calc(string s,ll k){
        if(s.size()==1){
            if(k==0||k==1||k==2)return k+1;
        }else if(s.size()==2){
            if(k==0)return 1;
            if(k==1)return s[0]==s[1]?1:2;
        }else if(s.size()==3){
            if(k==0)return s[0]!=s[1]||s[1]!=s[2];
        }
        var v=make_pair(s,k);
        if(f.count(v))return f[v];
        string nxt;
        ll ans=0;
        bool successful=true;
        for(int i=0;i<(int)s.size();i+=2){
            if(i<(int)s.size()-1&&s[i]==s[i+1]){
                successful=false;
                break;
            }
            nxt+=s[i];
        }
        if(successful)ans+=calc(nxt,s.size()%2?(k>>1):((k+1)>>1)),ans%=mod;
        nxt=s[0]^1;
        successful=true;
        for(int i=1;i<(int)s.size();i+=2){
            if(i<(int)s.size()-1&&s[i]==s[i+1]){
                successful=false;
                break;
            }
            nxt+=s[i];
        }
        if(successful)ans+=calc(nxt,s.size()%2?((k+1)>>1):(k>>1)),ans%=mod;
        return f[v]=ans;
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>t;
    while(t--)cin>>s>>k,cout<<QiFeng233::calc(s,k)%mod<<endl;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<string,ll> var;
int t;
const ll mod=1e9+9; 
string s;
ll k;
map<var,ll> f; 
namespace QiFeng233{
    ll calc(string s,ll k){
        if(s.size()==1){
            if(k==0||k==1||k==2)return k+1;
        }else if(s.size()==2){
            if(k==0)return 1;
            if(k==1)return s[0]==s[1]?1:2;
        }else if(s.size()==3){
            if(k==0)return s[0]!=s[1]||s[1]!=s[2];
        }
        var v=make_pair(s,k);
        if(f.count(v))return f[v];
        string nxt;
        ll ans=0;
        bool successful=true;
        for(int i=0;i<(int)s.size();i+=2){
            if(i<(int)s.size()-1&&s[i]==s[i+1]){
                successful=false;
                break;
            }
            nxt+=s[i];
        }
        if(successful)ans+=calc(nxt,s.size()%2?(k>>1):((k+1)>>1)),ans%=mod;
        nxt=s[0]^1;
        successful=true;
        for(int i=1;i<(int)s.size();i+=2){
            if(i<(int)s.size()-1&&s[i]==s[i+1]){
                successful=false;
                break;
            }
            nxt+=s[i];
        }
        if(successful)ans+=calc(nxt,s.size()%2?((k+1)>>1):(k>>1)),ans%=mod;
        return f[v]=ans;
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>t;
    while(t--)cin>>s>>k,cout<<QiFeng233::calc(s,k)%mod<<endl;
    return 0;
}