#include <bits/stdc++.h>
#include <atcoder/math>
using namespace std;
int main(){
  int T;
  cin >> T;
  for (int i = 0; i < T; i++){
    long long M, A, B, K;
    cin >> M >> A >> B >> K;
    long long L = lcm(A, B);
    if (K > A){
      cout << 0 << endl;
    } else if (K == A){
      long long ans = 0;
      if (K == A){
        ans += M / A - 1 - (M / B - M / L);
        if (M / B * B > M / A * A){
          ans++;
        }
      }
      cout << ans << endl;
    } else {
      long long ans = 0;
      vector<long long> r1 = {0, K}, m1 = {B, A};
      pair<long long, long long> P1 = atcoder::crt(r1, m1);
      if (P1.second != 0){
        if (P1.first <= M){
          ans += (M - P1.first) / P1.second + 1;
        }
        if (P1.first <= A + K - 1){
          ans -= (A + K - 1 - P1.first) / P1.second + 1;
        }
      }
      vector<long long> r2 = {0, K}, m2 = {A, B};
      pair<long long, long long> P2 = atcoder::crt(r2, m2);
      if (P2.second != 0){
        if (P2.first <= M){
          ans += (M - P2.first) / P2.second + 1;
        }
        if (P2.first <= B + K - 1){
          ans -= (B + K - 1 - P2.first) / P2.second + 1;
        }
      }
      cout << ans << endl;
    }
  }
}