样例不知道为什么输入了一半就结束了，后面就没有输出了喵。。（悲）

#include<bits/stdc++.h>
using namespace std;
long long t,x,k;
int d[]={1,0,0,0,1,0,1,0,2,1};
long long g(long long x,long long k){
	long long sum=0;
	while(x){
		sum+=d[x%10];
		x/=10;
	}
	if(k==1)
	    return sum;
	return g(sum,k-1);
}
int main(){
	cin>>t;
	while(t--){
		cin>>x>>k;
		cout<<g(x,k)<<endl;
	}
	return 0;
}