#include <bits/stdc++.h>

using namespace std;
using i64 = long long;

i64 n, m;
i64 d[10];

i64 get(i64 x)
{
    i64 res = 0;
    while (x)
    {
        res += d[x % 10];
        x /= 10;
    }
    return res;
}

void solve()
{
    cin >> n >> m;

    i64 res = n;
    while (m && res)
    {
        res = get(res);
        m--;
    }
    if (res == 0 && m % 2)
        res = 1;
    cout << res << '\n';
}

void init()
{
    d[0] = d[4] = d[6] = d[9] = 1;
    d[8] = 2;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    init();
    i64 T = 1;
    cin >> T;
    while (T--)
        solve();

    return 0;
}