#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
array<ll,3> f(ll n,ll m,ll a,ll b){
    assert(a>=0&&b>=0);
    ll a1=a/m,b1=b/m;
    a%=m,b%=m;
    ll k=(a*(n-1)+b)/m;
    array<ll,3> res{0,0,0};
    if(k){
        array<ll,3> tmp=f(k,a,m,m-b+a-1);
        res[0]+=k*n-tmp[0];
        res[1]+=k*k*n-2*tmp[2]-tmp[0];
        res[2]+=k*n*(n-1)/2+tmp[0]/2-tmp[1]/2;
        res[1]+=2*a1*res[2];
        res[1]+=2*b1*res[0];
    }
    res[0]+=n*(n-1)/2*a1+n*b1;
    res[1]+=a1*a1*(n-1)*n*(2*n-1)/6
        +2*a1*b1*n*(n-1)/2
        +b1*b1*n;
    res[2]+=a1*(n-1)*n*(2*n-1)/6
        +b1*n*(n-1)/2;
    return res;
}
#undef ll
void main(){
    cin>>n>>m>>a>>b;
    array<lll,3> res=f(n,m,a,b);
    array<lll,3> res2=f(n,m,a,0);

    cout<<(long long)(2*res[2]-(n-1)*res[0]-n*res2[0]+res2[2])<<endl;;
}
}
signed main(){
    int T=1;cin>>T;
    while(T--)GENSOKYO::main();
    // cout<<clock()<<endl;
    return 0;
}