#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <cstring>

#include <algorithm>

#include <set>

#include <map>

#include <queue>

#include <vector>

#include <string>

#define LL long long

using namespace std;

int a, b, d, n;

int main()

{

    //freopen("test.in", "r", stdin);

    int T, rest, to, pre;

    scanf("%d", &T);

    for (int times = ; times < T; ++times)

    {

        int ans = , tmp;

        scanf("%d%d%d%d", &a, &b, &d, &n);

        rest = to = ;

        pre = -;

        for (int i = ; i < n; ++i)

        {

            tmp = a*b+to;

            to = tmp/;

            rest = tmp%;

            if (tmp == pre)

            {

                if (rest == d) ans += n-i;

                break;

            }

            pre = tmp;

            if (rest == d) ans++;

        }

        if (to !=  && to == d) ans++;

        printf("%d\n", ans);

    }

    return ;

}