#include<iostream> #include<cassert> #include<atcoder/math> using namespace std; int gcd(int a,int b) { while(b) { int t=a%b; a=b; b=t; } return a; } long long M; int A,B,K; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T;cin>>T; for(;T--;) { cin>>M>>A>>B>>K; if(A<K) { cout<<"0\n"; continue; } int g=gcd(A,B); if(K%g!=0) { cout<<"0\n"; continue; } A/=g; B/=g; K/=g; M/=g; if(K==A) { long long lcm=(long long)A*B; long long ans=M/lcm*(B-A+1); M%=lcm; ans+=M/A-(M/A*A)/B; assert(ans>0); ans--; cout<<ans<<"\n"; continue; } long long ans=0; for(int t=0;t<2;t++,swap(A,B)) {//iA=-K mod B int i=(long long)-K*atcoder::inv_mod(A,B)%B; if(i<0)i+=B; if(M>=K) { long long lim=(M-K)/A-i; if(lim>=0)ans+=lim/B+1; } } cout<<ans<<"\n"; } }