/** \brief
 *
 * \param
 * \param
 * \return
 *

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

using namespace std;

int threediv(std::vector<int> &nums) {
    if (nums.size() < 2)
        return 0;

    int i = 0;
    int j = 1;
    int k = 2;

    int threedivs = 0;

    // N(NlogN)
    sort(nums.begin(), nums.end());

    // O(N)?
    bool move_k = false;
    bool move_j = false;
    for (int _ = 0; _ < 1000; ++_) {
        if (nums[j] % nums[i] == 0 && nums[k] % nums[j] == 0) {
            std::cout << "Triplet { " << nums[i] << ", " << nums[j] << ", " << nums[k] << " }\n";
            ++threedivs;
        }

        // Keep divisible pairs together as much as possible
        if (nums[j] % nums[i] == 0) {
            if (k < nums.size() - 1) {
                ++k;
                continue;
            }
            move_k = true;
        }

        // if (nums.size() - 1 == k) {
        //     // Move j to the right and do bounds check
        //     if (j < k - 1)
        //         ++j;
        //     move_j = true;
        //     if (j == k - 1 && k == nums.size() - 1)
        //         goto inc_i;
        //     continue;
        // }
inc_i:
        if (k - j > 1)
            ++j;
        else if (k < nums.size() - 1)
            ++k;
        else if (j - i > 1)
            ++i;

        // Reset j and k
        if (move_j) {
            j = i + 1;
            move_j = false;
        }

        if (move_k) {
            k = j + 1;
            move_k = false;
        }

        // We have just looked at the triplet with (i,j,k) = (-3,-2,-1)
        if (i >= j || j >= k || k >= nums.size())
            break;
    }

    return threedivs;
}


int main() {
    int n;
    std::vector<int> nums;
    nums.reserve(n);

    cin >> n;
    for (int _n = 0; _n < n; ++_n) {
        int num;
        cin >> num;
        nums.push_back(num);
    }

    int threedivs = threediv(nums);
    std::cout << threedivs;
}
*/

#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;
    }
}
