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

int g[10]={1,0,0,0,1,0,1,0,2,1};

int f(int x){
    int e=0;
    while(x){
        e+=g[x%10];
        x/=10;
    }
    return e;
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        int x,K;
        scanf("%d%d",&x,&K);

        while(x&&K){
            x=f(x);
            K--;
        } 

        if(!x){
            if(K&1) printf("1\n");
            else printf("0\n");
        }
        else printf("%d\n",x);
    }

    return 0;
}