#include <bits/stdc++.h>

int ff[] = {1, 0, 0, 0, 1, 0, 1, 0, 2, 1};

int f(int x) {
	int ans = 0;
	do {
		ans += ff[x % 10];
		x /= 10;
	} while(x);
	return ans;
}

void solve() {
	int x, k;
	std::cin >> x >> k;
	// k = 10;
	while (k--) {
		x = f(x);
		if (x == 0) break;
	}
	if (k % 2 == 1) {
		x = 1;
	}
	printf("%d\n", x);
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	int t;
	std::cin >> t;
	while (t--) {
		solve();
	}
}