#include<bits/stdc++.h>
using namespace std;
template<typename T>
void read(T &a){
    #define gc getchar()
    char c;a=0;int f=1;
    while(!isdigit(c=gc))if(c=='-')f=-1;
    do a=a*10+c-'0';
    while(isdigit(c=gc));
    a*=f;
}
template<typename T>
void write(T a){
    if(a<0)putchar('-'),a=-a;
    if(a>=10)write(a/10);
    putchar('0'+a%10);
}
char GC(){
    char c=getchar();
    while(c<=32)c=getchar();
    return c;
}
template<typename T>
void chmin(T &x,T y){if(x>y)x=y;}
template<typename T>
void chmax(T &x,T y){if(x<y)x=y;}
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef unsigned int ui;
typedef pair<int,int> PII;
typedef pair<ll,int> PLI;
typedef __int128 lll;
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
namespace GENSOKYO{
ll n,m,a,b;
#define ll lll
ll f(int p,int q,ll n,ll m,ll a,ll b){
    ll res=0;
    assert(a>=0&&b>=0);
    ll a1=a/m,b1=b/m;
    a%=m,b%=m;
    ll k=(a*(n-1)+b)/m;
    if(p==0&&q==1){
        res=n*(n-1)/2*a1+n*b1;
        if(k)res+=k*n-f(0,1,k,a,m,m-b+a-1);
    }else if(p==0&&q==2){
        if(a1||b1){
            res+=a1*a1*(n-1)*n*(2*n-1)/6;
            res+=2*a1*b1*n*(n-1)/2;
            res+=b1*b1*n;
            if(a1)res+=2*a1*f(1,1,n,m,a,b);
            if(b1)res+=2*b1*f(0,1,n,m,a,b);
        }
        if(k)res+=k*k*n-2*f(1,1,k,a,m,m-b+a-1)-
            f(0,1,k,a,m,m-b+a-1);
    }else if(p==1&&q==1){
        res+=a1*(n-1)*n*(2*n-1)/6;
        res+=b1*n*(n-1)/2;
        if(k)res+=k*n*(n-1)/2+f(0,1,k,a,m,m-b+a-1)/2
            -f(0,2,k,a,m,m-b+a-1)/2;
    }
    return res;
}
#undef ll
void main(){
    cin>>n>>m>>a>>b;
    cout<<(long long)(2*f(1,1,n,m,a,b)-(n-1)*f(0,1,n,m,a,b)-n*f(0,1,n,m,a,0)+f(1,1,n,m,a,0))<<endl;;
}
}
signed main(){
    int T=1;cin>>T;
    while(T--)GENSOKYO::main();
    cout<<clock()<<endl;
    return 0;
}