#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

int generate_next(int& org){
    int next = 0;
    while(org > 0){
        int curr = org % 10;
        next += (curr * curr);
        org = org / 10;
    }
    return next;
}

vector<int> generate_seq(int start, int size){

    vector<int> seq;
    seq.push_back(start);
    int next = generate_next(start);
    for(int i = 1; i < size; i++){
        seq.push_back(next);
        int curr = generate_next(next);
        next = curr;
    }
    return seq;
}

int how_many(vector<int> seq, int num){

    int counter = 0;

    for(int i = 0; i < seq.size(); i++){
        if(seq.at(i) == num){
            counter++;
        }
    }
    return counter;
}

int main()
{
    int v, t, n, a, index = 0;
    vector<int> counters;

    cin >> t;

    for(int i = 0; i < t; i++){
        cin >> a >> v >> n;
        vector<int> seq = generate_seq(a, n);
        counters.push_back(how_many(seq, v));
    }
    for(int i = 0; i < counters.size(); i++){
        cout << counters.at(i) << endl;
    }
    return 0;
}
