#include <bits/stdc++.h>
#define rep(i, a, b) for (auto cc##i = (b), i = (a); i <= cc##i; ++i)
#define per(i, a, b) for (auto cc##i = (b), i = (a); i >= cc##i; --i)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;

const int w[] = {1, 0, 0, 0, 1, 0, 1, 0, 2, 1};

int g(int x, int k) {
  if (!k) return x;
  if (x == 0) return (k & 1) ? 1 : 0;
  if (x == 1) return (k & 1) ? 0 : 1;
  int y = x, v = 0;
  do {
    v += w[y % 10];
    y /= 10;
  } while (y);
  return g(v, k - 1);
}

void solve() {
  int x, k;
  cin >> x >> k;
  cout << g(x, k) << "\n";
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int t;
  cin >> t;
  while (t--) solve();
  return 0;
}