#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define pii pair<int, int>
#define ld long double
#define all(a) (a).begin(), (a).end()

vector<int> t = {1, 0, 0, 0, 1, 0, 1, 0, 2, 1};

int f(int x) {
    if (x == 0) return 1;
    int res = 0;
    while (x) {
        res += t[x % 10];
        x /= 10;
    }
    return res;
}

void solve() {
    int x, k;
    cin >> x >> k;

    while (x != 0 && k != 0) {
        x = f(x);
        --k;
    }

    if (k == 0) {
        cout << x << '\n';
        return;
    }

    cout << (k % 2 == 0 ? 0 : 1) << '\n';
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;
    while (t--) solve();

    return 0;
}