#include <iostream>

using namespace std;

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

int main(){

    int t;
    cin >> t;

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

        int countt = 0;

        int numInCycle = -1;
        for(int k=0; k<8; k++){
            if(v == cycle[k]) numInCycle = k+1;
        }

        for(int 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;

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

            if(a == v) countt++;

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


    return 0;
}

