#include <iostream>
#include <algorithm>
#include <vector>
#define endl '\n'
using namespace std;

int binarySearch(vector<int> vec, int l, int r, int key) {
    int mid;
    int output = -1;

    while (l <= r) {
        mid = (l + r)/2;
        if (key == vec[mid]) {
            output = mid;
            l = r + 1;
        } else if (key > vec[mid]) {
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }

    return output;
}

int rule(int n) {
    int sum = 0;
    int digit;

    while (n > 0) {
        digit = n%10;
        sum += digit*digit;
        n /= 10;
    }

    return sum;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

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

        int total = 0;

        vector<int> sequence;
        int iRepL = -1;
        int iRepR = -1;

        sequence.push_back(a);

        for (int i = 1, newA; i < n; i++) {
            newA = rule(sequence[i - 1]);

            int bs = binarySearch(sequence, 0, sequence.size(), newA);
            if (bs != -1) {
                iRepL = bs;
                iRepR = i - 1;

                break;
            }

            sequence.push_back(newA);
        }

        if (iRepL == -1) {
            total = count(sequence.begin(), sequence.end(), v);
        } else {
            if (iRepL != 0) total += count(sequence.begin(), sequence.begin() + iRepL, v);

            int countRep = count(sequence.begin() + iRepL, sequence.begin() + iRepR + 1, v);
            total += countRep*((n - iRepL)/(iRepR - iRepL + 1));

            if ((n - iRepL)%(iRepR - iRepL + 1) != 0) total += count(sequence.begin() + iRepR + 1, sequence.end(), v);
        }

        cout << total << endl;
    }

    return 0;
}
