#include <bits/stdc++.h>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    long long t;
    cin >> t;
    while (t--)
    {
        long long a,b,l;
        cin>>a>>b>>l;
        long long x = 1;
        set<long long> h;
        for(long long i = 0;i<100;i++){
            if(x>l) break;
            if(l%x) continue;
            long long r = l/x;
            long long y = 1;
            for(long long j = 0;j<100;j++){
                if(y>r) break;
                if(r%y) continue;
                long long ans = r/y;
                h.insert(ans);
                y*=b;
            }
            x*=a;

        }
        long long total = h.size();
        cout<<total<<endl;
        
    }
}