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

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;
        if (a == v) total++;

        int next = a;
        int repeat = -1;
        int members = 0;

        bool visited[649] = {false};

        for (int i = 1; i < n; i++) {
            next = rule(next);

            members++;
            if (next == v) total++;

            if (visited[next] == true) {
                repeat = next;
                break;
            } else if (next == a) {
                repeat = a;
                break;
            } else {
                visited[next] = true;
            }
        }

        if (repeat != -1) {
            if (repeat == a) {
                if (repeat == v) total--;
                total *= n/members;
                if (n%members != 0) {
                    for (int i = 0, last = repeat; i < n%members; i++) {
                        if (last == v) total++;
                        last = rule(last);
                    }
                }
            } else if (repeat == v) {
                total--;
                int temp = a;
                int withdrawMembers = 0;
                while (temp != repeat) {
                    members--;
                    withdrawMembers++;
                    temp = rule(temp);
                }
                total *= (n - withdrawMembers)/members;
                if (n%members != 0) {
                    for (int i = 0, last = repeat; i < (n - withdrawMembers)%members; i++) {
                        if (last == v) total++;
                        last = rule(last);
                    }
                }
            } else {
                int temp = a;
                int withdrawMembers = 0;
                int vBeforeRep = 0;
                while (temp != repeat) {
                    withdrawMembers++;
                    if (temp == v) {
                        vBeforeRep++;
                    }
                    temp = rule(temp);
                }
                total -= vBeforeRep;
                total *= (n - withdrawMembers)/members;
                if (n%members != 0) {
                    for (int i = 0, last = repeat; i < (n - withdrawMembers)%members; i++) {
                        if (last == v) total++;
                        last = rule(last);
                    }
                }
                total += vBeforeRep;
            }
        }

        cout << total << endl;
    }

    return 0;
}
