//
// Created by Barichek on 22.07.2023 10:34:30
//

#include <bits/stdc++.h>

#define F first
#define S second
#define MP make_pair
#define PB push_back

#define all(a) a.begin(), a.end()
#define len(a) (int) (a.size())
#define mp make_pair
#define pb push_back
#define fir first
#define sec second

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;

#ifdef Energy_is_not_over
#define DEBUG for (bool ____DEBUG = true; ____DEBUG; ____DEBUG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl

template<class ...Ts>
auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }

#else
#define DEBUG while (false)
#define LOG(...)
#endif

const int max_n = -1, inf = 1000111222;

int ff(int xx)
{
    if (xx==8){
        return 2;
    }
    if (xx==0 || xx==4 || xx==6 || xx==9){
        return 1;
    }
    return 0;
}

int f(int x)
{
    if (x==0){
        return 1;
    }
    int res=0;
    while (x){
        res+=ff(x%10);
        x/=10;
    }
    return res;
}

void solve()
{
    int x,k;
    cin>>x>>k;
    for (int i=0;i<10&&k>0;i++){
        x=f(x);
        k--;
    }
    if (k%2==1){
        x^=1;
    }
    cout<<x<<"\n";
}

int main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int tests;
    cin>>tests;
    while (tests--){
        solve();
    }
    return 0;
}