#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define endl '\n'

using namespace std;

int t;
void read()
{
    cin >> t;
}

int nxt(int x)
{
    int ans = 0;
    while (x)
    {
        int dig = x % 10;
        x /= 10;

        ans += dig * dig;
    }

    return ans;
}

int pos[800];
void solve()
{
    while (t--)
    {
        int a, v, n;
        cin >> a >> v >> n;

        memset(pos, -1, sizeof(pos));
        int idx = 2, last = nxt(a);
        pos[last] = idx;
        for (;;)
        {
            idx++;
            last = nxt(last);
            if (pos[last] == -1)
                pos[last] = idx;

            else
                break;
        }

        int from = pos[last], len = idx - from;
        if (v >= 800 || pos[v] == -1)
        {
            if (v == a)
                cout << 1 << endl;

            else
                cout << 0 << endl;

            continue;
        }

        if (pos[v] < from)
        {
            int ans = 0;
            if (v == a)
                ans++;

            if (n >= pos[v])
                ans++;

            cout << ans << endl;
            continue;
        }

        else
        {
            int ans = 0;
            if (v == a)
                ans++;

            n -= from - 1;
            if (n <= 0)
                continue;

            ans += n / len;
            if (n % len >= pos[v] - from + 1)
                ans++;

            cout << ans << endl;
        }
    }
}

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

    read();
    solve();
}
