#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll a[10] = {1,0,0,0,1,0,1,0,2,1};
ll f(ll n)
{
    if(n == 0) return 1;
    ll ret = 0;
    while(n)
    {
        ret += a[n%10];
        n /= 10;
    }
    return ret;
}
int main()
{
    ll z;
    cin >> z;
    while(z--)
    {
        ll n, k;
        cin >> n >> k;
        for(ll i=0; i<min(k, 40ll); i++)
            n = f(n);
        if(k <= 40) cout << n << '\n';
        else cout << (k+n) % 2 << '\n';
    }
    return 0;
}