#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;

int x,k;
int f[]={1,0,0,0,1,0,1,0,2,1};
int fun(int x){
    if(x==0) return 1;
    int res=0;
    while(x)
    {
        int temp=x%10;
        temp=f[temp];
        res+=temp;
        x/=10;
    }
    return res;
}
void solve() {
    cin>>x>>k;
    while(k)
    {
        k--;
        x=fun(x);
        if(x==0) break;
    }
    if(k==0)
    {
        cout<<x<<endl;
        return ;
    }
    if(k%2) cout<<"1\n";
    else cout<<"0\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t = 1;
    cin >> t;
    while (t--) solve();
    return 0;
}