#include <iostream>
#include <vector>

using namespace std;



vector<unsigned long> numbers(unsigned long number)
{
    vector<unsigned long> res;
    while (number != 0)
    {
        res.push_back(number % 10);
        number /= 10;
    }

    return res;
}

int main()
{
    unsigned long N = 0;
    cin >> N;

    unsigned long arr[N][3] = {{0}};
    for (unsigned long i = 0; i < N; ++i)
        for (unsigned short j = 0; j < 3; ++j)
            cin >> arr[i][j];

    // unsigned long N = 2;
    // unsigned long arr[N][3] = {{13, 1, 10}, {4, 8, 20}};


    unsigned long res[N] = {0};
    for (unsigned long i = 0; i < N; ++i)
    {
        vector<unsigned long> sequence;
        sequence.push_back(arr[i][0]);
        unsigned long firstNum = arr[i][0];
        unsigned long seqRes = firstNum;
        unsigned long breakedAt = 0;
        for (unsigned long j = 0; j < (arr[i][2] - 1); ++j)
        {
            vector<unsigned long> nums = numbers(seqRes);
            seqRes = 0;
            for (unsigned int f = 0; f < nums.size(); ++f)
            {
                seqRes += nums[f] * nums[f];
            }
            sequence.push_back(seqRes);
            // cout << "first num: " << firstNum << " seqRes: " << seqRes << endl;
            if (firstNum == seqRes)
            {
                breakedAt = j;
                break;
            }
        }
        for (unsigned long k = 0; k < sequence.size(); ++k)
        {
            // cout << "{" << sequence[k] << ", " << arr[i][1] << "}";
            // cout << ' ' << sequence[k] == arr[i][1];
            if (sequence[k] == arr[i][1])
                res[i] ++;
            // cout << endl;
        }
        // cout << "breaked at: " << breakedAt << endl;
        if (breakedAt != 0)
        {
            res[i] += arr[i][2] / breakedAt + 1;
        }
    }
    for (unsigned long i = 0; i < N; ++i)
    {
        cout << res[i] << endl;
    }
    return 0;
}