#include<iostream>
using namespace std;

int broiTestove;

int parvoChislo;
int koeChislo;
int kolkoCHisla;

int sumaOtKvadrNCifriNa(int chislo){

    int suma = 0;

    int kopieChislo = chislo;

    while(kopieChislo > 0){
        int cifra = kopieChislo%10;

        suma += cifra*cifra;

        kopieChislo /= 10;
    }

    return suma;
}

int main(){

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

    cin>>broiTestove;

    for(int t = 0; t < broiTestove; t++){
        cin>>parvoChislo>>koeChislo>>kolkoCHisla;

        int segashnoChislo = parvoChislo;

        int broicheTuka = 0;

        if(segashnoChislo == koeChislo){
            broicheTuka++;
        }

        for(int i = 1; i < kolkoCHisla; i++){
            segashnoChislo = sumaOtKvadrNCifriNa(segashnoChislo);

            if(segashnoChislo == koeChislo){
                broicheTuka++;
            }
        }

        cout<<broicheTuka<<endl;
    }

    return 0;
}
