#include <bits/stdc++.h>
using namespace std;
#ifndef LOCAL
#define cerr if(false) cerr
#endif
#define endl "\n"
typedef long long ll;
template<class T, class T2> inline ostream &operator <<(ostream &out, const pair<T, T2> &x) { out << x.first << " " << x.second; return out;}
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e9 + 7;

const ll MAX_N = 1e3 + 10;

ll digsum(ll x) {
    ll ret = 0;
    while(x) {
        ret += (x % 10ll) * (x % 10ll);
        x /= 10;
    }
    return ret;
}

ll ind[MAX_N];

ll solve(ll a, ll v, ll n) {
    for(ll i = 0; i < MAX_N; i ++) {
        ind[i] = -1;
    }

    if(a > MAX_N && v > MAX_N) {
        if(a == v) {
            return 1;
        } else {
            return 0;
        }
    } else if(v > MAX_N) {
        return 0;
    } else if(n == 1) {
        if(a == v) {
            return 1;
        } else {
            return 0;
        }
    }


    ll ret = (a == v);
    a = digsum(a);
    n -= 1;

    ll curr = a;
    ll len = 0;

    while(n > 0) {
        if(ind[curr] != -1) {
            break;
        }
        ind[curr] = len;
        len ++;
        ret += (curr == v);
        n --;
        curr = digsum(curr);
    }

    if(n == 0) {
        return ret;
    }

    if(ind[v] == -1 || ind[v] < ind[curr]) {
        return ret;
    }

    ll cyclelen = len - ind[curr];
    if(n % cyclelen == 0) {
        ret += n / cyclelen;
    } else {        
        ret += n / cyclelen + ((n - 1) % cyclelen >= ind[v] - ind[curr]);
    }
    return ret;
}

ll solveslow(ll a, ll v, ll n) {
    ll ret = 0;
    for(int i = 0; i < n; i ++) {
        if(a == v) {
            ret ++;
        }
        a = digsum(a);
    }
    return ret;
}

signed main() {
#ifndef LOCAL
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#endif

    ll t;
    cin >> t;
    while(t --) {
        ll a, v, n;
        cin >> a >> v >> n;
        cout << solve(a, v, n) << endl;; 
    }

    return 0;

    while(true) {
        ll a = rand() % (100), v = rand() % (100), n = rand() % 1000 + 1;
        ll slow = solveslow(a, v, n), fast = solve(a, v, n);
        if(slow != fast) {
            cout << a << " " << v << " " << n << endl;
            cout << slow << " " << fast << endl;
            return 0;
        }
        cout << slow << " " << fast << endl;
    }

    return 0;
}
