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

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

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

  auto f = [&](int x)->int {
    if (x == 0) return 1;
    int ans = 0;
    while(x) {
      int dig = x%10;
      x /= 10;
      ans += F[dig];
    }
    return ans;
  };

  int tt;
  cin >> tt;
  while(tt--) {
    int x, k;
    cin >> x >> k;
    while(x && k) {
      k--;
      x = f(x);
    }
    if (k == 0) {
      cout << x << '\n';
      continue;
    }
    assert(x == 0);
    if (k%2 == 1) {
      cout << 1 << '\n';
    } else {
      cout << 0 << '\n';
    }
  }

}