#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define MULT_TEST 1
using namespace std;
typedef long double ldb;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f;
const int MOD = 998244353;
int val[10] = {1, 0, 0, 0, 1, 0, 1, 0, 2, 1};
inline int read() {
    int w = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        w = (w << 1) + (w << 3) + ch - 48;
        ch = getchar();
    }
    return w * f;
}
inline void Solve() {
    int x, k, ans = -1;
    x = read(); k = read();
    for (int i = 1; i <= k; i++) {
        if (x == 1 || x == 0) {
            ans = x ^ ((k - i + 1) & 1);
            break;
        }
        int sum = 0;
        for (int j = 0, cp = x; j <= 10 && cp; j++) {
            sum += val[cp % 10];
            cp /= 10;
        }
        x = sum;
    }
    if (ans == -1) printf("%lld\n", x);
    else printf("%lld\n", ans);
}
signed main() {
    int _ = 1;
#if MULT_TEST
    _ = read();
#endif 
    while (_--) Solve();
    return 0;
}