#include <bits/stdc++.h>

using i64 = long long;

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

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

int g(int x, int k) {
	if (k == 0) {
		return x;
	}
	if (x >= 2) {
		return g(f(x), k - 1);
	}
	return (x + k) % 2;
}

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

	std::cout << g(x, k) << "\n";
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int T;
	std::cin >> T;

	while (T--) {
		solve();
	}

	return 0;
}