#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pi pair<int,ll>
#define fi first
#define se second
#define pb push_back
#pragma GCC optimize("O3")
#pragma GCC target("avx2")

int cal(int x){
    int ret=0;
    while(x){
        int dg=x%10;
        if(dg==8){
            ret+=2;
        }
        if(dg==0||dg==4||dg==6||dg==9)ret++;
        x/=10;
    }
    return ret;
}

int rec(int x,int k){
    if(k==0)return x;
    return rec(cal(x),k-1);
}

int main(){
    int t;cin>>t;
    while(t--){
        int x,k;cin>>x>>k;
        cout<<rec(x,k)<<endl;
    }
}