#include <iostream>
#include <cmath>
using namespace std;
int convert(int n){
    if(n<10){
        return n*n;
    }
    if(n<100){
        return (n%10)*(n%10)+(n/10)*(n/10);
    }
    return (n%10)*(n%10)+((n/10)%10)*((n/10)%10) + (n/100)*(n/100);
}
long long t, n, v, res;
int cycle[8]={4, 16, 37, 58, 89, 145, 42, 20};
string a;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cin>>t;
for(int x=0;x<t;x++){
    res=0;
    cin>>a>>v>>n;
    string p;
    long long pastV=v;
    while(pastV!=0){
        p.push_back(pastV%10+48);
        pastV=pastV/10;
    }
    string p1;
    for(int i=p.size()-1;i>=0;i--){
        p1.push_back(p[i]);
    }
    if(p1==a){
        res++;
    }
    if(v>729 or n==1){
        cout<<res<<"\n";
        continue;
    }
    int ans=0;
    for(int j=0;j<a.size();j++){
        int num = a[j]-48;
        ans=ans+num*num;
    }
    int i;
    for(i=2;i<20 and i<=n;i++){
        if(ans==v){
            res++;
        }
        ans=convert(ans);
    }
    if(i>n){
        cout<<res<<"\n";
        continue;
    }
    if(ans!=1 and v==1){
        cout<<res<<"\n";
        continue;
    }
    if(ans==1 and v!=1){
        cout<<res<<"\n";
        continue;
    }
    if(ans==1 and v==1){
        cout<<res+n-19<<"\n";
        continue;
    }
    if(v!=16 and v!=4 and v!=37 and v!=58 and v!=89 and v!=145 and v!=42 and v!=20){
        cout<<res<<"\n";
        continue;
    }
    bool started=false;
    for(int j=0;j<8;j++){
        if(cycle[j]==ans){
            started=true;
        }
        if(started){
            if(cycle[j]==v){
                res++;
                cout<<res+(n-i)/8<<"\n";
                break;
            }
            i++;
        }
        if(j==7){
            j=0;
        }
    }
}
return 0;
}

