#include<bits/stdc++.h>
using namespace std;
int T;
const int a[] = {1, 0, 0, 0, 1, 0, 1, 0, 2, 1};
int n, k;
int dfs(int x, int k) {
    if(k == 0) return x;
    if(x == 0) {
        if(k & 1) return 1;
        else return 0;
    }
    int sum = 0;
    while(x) sum += a[x % 10], x /= 10;
    return dfs(sum, k - 1);
}
void solve() {
    scanf("%d%d", &n, &k);
    int ans = 1;
    printf("%d\n", dfs(n, k));
}
int main() {
    cin >> T;
    while(T--) solve();
    return 0;
}