#include <iostream>
#define ll long long
#define endl "\n"
using namespace std;


int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
    ll t;
    cin >> t;
    while(t>0){
        ll a,v,n,ans=0,cicle4=8,pos,br=0;
        bool in=false,four=false;
        cin >> a >> v >> n;
        for(ll i=0;i<n;i++){
            if(a==1){
                if(v==1){
                    ans+=n-i;
                }
                break;
            }
            br++;
            if(a==v){
                if(four){
                    pos=br;
                    in=true;
                }
                ans++;
            }
            if(a==4){
                br=0;
                if(four){
                    if(in){
                        ans+=(n-i)/8;
                        if(pos+1<=(n-i)%8){
                            ans++;
                        }
                    }
                    break;
                }else{
                    four=true;
                }
            }
            ll curra=a;
            a=0;
            while(curra!=0){
                ll cifr=curra%10;
                a+=cifr*cifr;
                curra/=10;
            }
        }
        cout << ans << endl;
        t--;
    }
return 0;
}


