#include <stdio.h>
#include <iostream>

using namespace std;

int T;

int a;
int v;
int n;

int i;
int j;

int sumDS(int num) {
    int result = 0;
    for(; num != 0; num = num/10) {
        result += (num % 10)*(num % 10);
    }
    return result;
}

int sequence(int a, int v, int n) {
    int result = 0;
    int previous = a;

    for(i = 1; i <= n; i++) {
        if(previous == v) {
            result++;
        }
        previous = sumDS(previous);
    }
    return result;
}

int main() {
    scanf("%d", &T);
    int sequence_results[T];

    int A[T];
    int V[T];
    int N[T];

    for(i = 0; i < T; i++) {
        scanf("%d", &a);
        scanf("%d", &v);
        scanf("%d", &n);

        A[i] = a;
        V[i] = v;
        N[i] = n;
    }

    for(int j = 0; j < T; j++) {
        printf("%d\n", sequence(A[j], V[j], N[j]));
    }

    return 0;
}