#include <iostream>
#include <vector>

using namespace std;

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

    return res;
}

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

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

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


    int res[N] = {0};
    for (unsigned int i = 0; i < N; ++i)
    {
        vector<unsigned int> sequence;
        unsigned int seqRes = arr[i][0];
        for (unsigned int j = 0; j < (arr[i][2] - 1); ++j)
        {
            vector<unsigned int> nums = numbers(seqRes);
            seqRes = 0;
            for (int f = 0; f < nums.size(); ++f)
            {
                seqRes += nums[f] * nums[f];
            }
            sequence.push_back(seqRes);
        }
        for (unsigned int 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;
        }
    }
    for (unsigned int i = 0; i < N; ++i)
    {
        if (i == (N - 1)){
            cout << res[i];
            break;
        }
        cout << endl;
    }
    return 0;
}