#include <bits/stdc++.h>
using namespace std;

int pos [750];

int main (){

    int t;
    cin >> t;
    while (t --){

        for (int i = 1; i <= 730; i ++) pos [i] = 0;
        int a, v, n;
        cin >> a >> v >> n;
        int prev = 0, nxt = a, cnt = 1;
        do{
            if (nxt <= 730) pos [nxt] = cnt;
            cnt ++;
            swap (prev, nxt);
            while (prev > 0){
                nxt += (prev % 10) * (prev % 10);
                prev /= 10;
            }
        }while (pos [nxt] == 0);
        if (v != a && (v > 730 || pos [v] == 0 || pos [v] > n)) cout << "0\n";
        else if (v <= 730 && pos [v] < pos [nxt] || v > 730 && v == a) cout << "1\n";
        else{
            n -= pos [v] - 1;
            int loop = cnt - pos [nxt];
            cout << (n + loop - 1) / loop;
        }
    }

}
