#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128_t int128;
typedef pair<int, int> pii;
#define iofast ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define lowbit(x) (x&(-x))
#define inv(x) qpow(x,mod-2)
#define debug(x) cout << (#x) << " = " << x << endl
#define range(x) (x).begin(), (x).end()

const int iINF = 0x3f3f3f3f;
const ll llINF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;

/*---------------------------------------*/
int cal(const string& s)
{
    int ans = 0;
    for (const auto& c : s) {
        if (c == '0' || c == '4' || c == '6' || c == '9')
            ans += 1;
        else if (c == '8')
            ans += 2;
    }

    return ans;
}
void solve()
{
    int x, k;
    cin >> x >> k;
    if (k == 0) {
        cout << x << '\n';
        return;
    }
    string s = to_string(x);

    int ans;
    do {
        ans = cal(s);
        s = to_string(ans);
        k--;
    } while (k && ans);

    cout << (ans ^ (k & 1)) << '\n';
}

/*---------------------------------------*/

int main()
{
    iofast;
    int t = 1;
    cin >> t;
    while (t--)
        solve();

    return 0;
}