#include<iostream> using namespace std; int exgcd(int a,int b,int &x,int &y) { if(b==0) { x=1; y=0; return a; } int r=exgcd(b,a%b,x,y); int t=x; x=y; y=t-a/b*y; return r; } int fuck(int a,int b,int c,int &x,int &y) { int d=exgcd(a,b,x,y); if(c%d) return 0; int count=0; int k=c/d; x*=k;y*=k; int tempx=x,tempy=y; int b1=b/d,a1=a/d; // cout<<"!x="<<x<<" y="<<y<<endl; while(y>0) { // cout<<"*x="<<x<<" y="<<y<<endl; x+=b1; y-=a1; if(x>0&&y>0) count++; } while(tempx>0) { tempx-=b1; tempy+=a1; // cout<<"+x="<<tempx<<" y="<<tempy<<endl; if(tempy>0&&tempx>0) count++; } //cout<<count<<"::"<<endl; return count; } int main() { int a,b,c,x,y; int T; cin>>T; while(T--) { cin>>a>>b>>c; cout<<fuck(a,b,c,x,y)<<endl; } return 0; }