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

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

void solve(){
    int n,k;
    cin >> n >> k;
    for(int i = 1;i <= k;i ++){
        if(!n){
            cout << (((k - i) & 1) ? 0 : 1) << '\n';
            return;
        }
        int m = 0;
        while(n){
            m += c[n % 10];
            n /= 10;
        }
        n = m;
    }
    cout << n << '\n';
}

int main(){
    ios::sync_with_stdio(false);
    int TC;
    cin >> TC;
    while(TC --) solve();
    return 0;
}