#include <iostream>

using namespace std;

int cycle[8] = {4, 16, 37, 58, 89, 145, 42, 20};

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    long long t;
    cin >> t;

    for(long long i=0; i<t; i++){
        long long a, v, n;
        cin >> a >> v >> n;

        long long countt = 0;

        int numInCycle = -1;
        for(int k=0; k<8; k++){
            if(v == cycle[k]) numInCycle = k+1; ///num in cycle, WHEN CYCLE BEGINS AT 4
        }

        for(long long j=1; j<=n; j++){

            if(a == 1){
                if(v == 1) countt = n-j+1;
                break;
            }

            bool flag = false;
            for(int k=0; k<8; k++){
                if(a!=cycle[k]) continue;
                flag = true;

                if(numInCycle == -1) break;
                if(k+1 <= numInCycle) numInCycle = numInCycle - (k+1) + 1;  ///fixing the num in cycle that does not necessarily begin at 4
                else numInCycle = 8 - (k+1) + 1 + numInCycle;

                long long numFullCycles = (n-j+1)/8;
                long long remainder = (n-j+1)%8;
                countt = numFullCycles;
                if(numInCycle <= remainder) countt++;
            }
            if(flag) break;

            if(a == v) countt++;

            long long newA = 0;
            while(a>0){
                newA += (a%10)*(a%10);
                a /= 10;
            }
            a = newA;
        }
        cout << countt << endl;
    }

    return 0;
}

