#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

int sum_of_squared_digits(int num) {
    int sum = 0;
    while (num) {
        int dig = num % 10;
        sum += (dig * dig);
        num /= 10;
    }
    return sum;
}

int sequence(int a, int v, int n) {
    int occ = 0;

    for (int i = 0; i < n - 1; ++i) {
        a = sum_of_squared_digits(a);
        if (a == v) {
            ++occ;
        }
    }

    return occ;
}


int main() {
    int T;
    int a;
    int v;
    int n;

    cin >> T;
    for (int _t = 0; _t < T; ++_t) {
        cin >> a;
        cin >> v;
        cin >> n;
        int occ = sequence(a, v, n);
        std::cout << occ;
    }
}
