#include <stdio.h>
#include <string.h>

constexpr int calc(int x) {
	if (x == 8) {
		return 2;
	}
	if (x == 0 || x == 4 || x == 6 || x == 9) {
		return 1;
	}
	return 0;
}

constexpr int F(int x, int n) {
	if (!n) {
		return x;
	}
	if (x < 2) {
		return x ^ (n & 1);
	}
	int y = 0;
	while (x) {
		y += calc(x % 10);
		x /= 10;
	}
	return F(y, n - 1);
}

int main() {
	int task;
	for (scanf("%d", &task); task--; ) {
		int x, k;
		scanf("%d%d", &x, &k);
		printf("%d\n", F(x, k));
	}
	return 0;
}