stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;



#define   ll     long long int



void sortt(ll &a, ll &b, ll &c)

{

    if (a < b) swap(a, b);

    if (b < c) swap(c, b);

    if (a < b) swap(a, b);

}



ll func(ll h, ll w)

{

    ll i, j, k, s = 1e15;

    ll first, second, third;

    ll w_second = w / 2;

    ll w_third = w - w_second;



    for (i = 1; i < h; i++) {

        first = i * w;

        j = h - i;

        second = j * w_second;

        third = j * w_third;

        sortt(first, second, third);

        s = min(s, first - third);



        first = i * w;

        ll h_second = j / 2;

        ll h_third = j - h_second;

        second = h_second * w;

        third = h_third * w;

        sortt(first, second, third);

        s = min(s, first - third);

        //cout << i << ' ' << first << ' ' << second << ' ' << third << '\n';

    }

    return s;

}



int main( )

{

    ll h, w;

    cin >> h >> w;

    if (h % 3 == 0 || w % 3 == 0) {

        cout << "0\n";

        return 0;

    }

    cout << min(func(h, w), func(w, h)) << '\n';

    return 0;

}


// Optimized solution to the same problem (faster):
/*

    把h*w矩形分为三部分,求最大面积与最小面积之差最小值

    首先,n或m为三的倍数,面积差最小值为0

    其次,暴力枚举所有情况

    先将矩形,分为两部分,横切或者竖切,剩下的那块对半分

    最大h*w会爆int

*/

#include<cstdio>

#include<algorithm>

using namespace std;

typedef long long ll;

const ll inf = 9e18;

ll Max(ll a,ll b,ll c){

    return max(a, max(b, c));

}

ll Min(ll a,ll b,ll c){

    return min(a, min(b, c));

}

int main(){

    ll h, w, ans;

    scanf("%lld%lld", &h, &w);

    if(!(h%3)||!(w%3)){

        puts("0");

        return 0;

    }

    ans = inf;

    for (ll i = 1; i < h;i++){

        ll tmp = h - i;//剩下部分

        ll h1 = (tmp + 1) / 2;  //向上取整

        ll h2 = tmp / 2;//向下取整

        //为1时不能再横切

        if(tmp!=1){

            ans=min(ans,Max(i*w,h1*w,h2*w)-Min(i*w,h1*w,h2*w));

        }

        ll w1 = (w + 1) / 2;

        ll w2 = w / 2;

        //竖切,w初始为2

        ans=min(ans,Max(i*w,tmp*w1,tmp*w2)-Min(i*w,tmp*w1,tmp*w2));

    }

    for (ll i = 1; i < w;i++){

        ll tmp = w - i;//

        ll w1 = (tmp + 1) / 2;  //向上取整

        ll w2 = tmp / 2;//向下取整

        if(tmp!=1){

            ans=min(ans,Max(i*h,w1*h,w2*h)-Min(i*h,w1*h,w2*h));

        }

        ll h1 = (h + 1) / 2;

        ll h2 = h / 2;

        ans=min(ans,Max(i*h,tmp*h1,tmp*h2)-Min(i*h,tmp*h1,tmp*h2));

    }

    printf("%lld", ans);

    return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream> 

#include <algorithm>

using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)



int main() {

	int n, k, x,y=0;

	cin >> n >> k;

	rep(i, n) {

		cin >> x;

		if (x > k) {

			y += (x - k) * 2;

		}

		else if (k - x < x) {

			y += (k - x) * 2;

		}

		else {

			y += x * 2;

		}

	}

	cout << y << endl;

	return 0;

}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<algorithm>

using namespace std;

const int MAX_N = 100;

int N, K;

int X[MAX_N];

int main(){

scanf("%d", &N);

scanf("%d", &K);

for(int i = 0; i < N; ++i){

scanf("%d", X + i);

}

int ans = 0;

for(int i = 0; i < N; ++i){

int tmp = min(X[i], K - X[i]);

ans += tmp;

}

printf("%d\n", ans * 2);

return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<algorithm>

#include<iostream>

#include<cstdio>

#include<cstring>

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define MAXN 1000010

int  arr[1000];

int brr[101][101]={0};

int main()

{

	int n ;

	cin >>n;

	int sum=0;int pp = 0;

	if(n%2){

        pp = n-1;

	}

	else pp = n;



    for(int i=1;i<=n;i++){

        for(int j =1;j<=n;j++){

                if(j!=pp&&(brr[i][j]==0&&brr[j][i]==0)&&i!=j)

                    brr[i][j]=1,sum++;

        }

        pp--;

    }

    cout<<sum<<endl;

    for(int i=1;i<=n;i++){

        for(int j=1;j<=n;j++){

            if(brr[i][j])

                cout<<i<<" "<<j<<endl;

        }

    }

	return 0;

}


// Optimized solution to the same problem (faster):
#include <cstdio>

#include <algorithm>

int doing(int n) {

	

}

int main() {

	int n;

	scanf("%d",&n);

	int cnt=0;

	for(int i=1;i<=n;++i) {

		for(int j=i+1;j<=n;++j) {

			if(j!=n-i+(n+1)%2) {

				++cnt;

			}

		}

	}

	printf("%d\n",cnt);

	for(int i=1;i<=n;++i) {

		for(int j=i+1;j<=n;++j) {

			if(j!=n-i+(n+1)%2) {

				printf("%d %d\n",i,j);

			}

		}

	}

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<cstdio>

#include<vector>

using namespace std;

int n;

int main()

{

	scanf("%d", &n);

	int x = (n & 1) ? n : (n + 1);

	vector<pair<int, int>> edges;

	for (int i = 1; i <= n; i++)

	{

		for (int j = i + 1; j <= n; j++)

		{

			if (i + j != x)

			{

				edges.push_back(make_pair(i, j));

			}

		}

	}

	printf("%d\n", edges.size());

	for (auto& p : edges) printf("%d %d\n", p.first, p.second);

	return 0;

}


// Optimized solution to the same problem (faster):
#include <cstdio>

#include <algorithm>

int doing(int n) {

	

}

int main() {

	int n;

	scanf("%d",&n);

	int cnt=0;

	for(int i=1;i<=n;++i) {

		for(int j=i+1;j<=n;++j) {

			if(j!=n-i+(n+1)%2) {

				++cnt;

			}

		}

	}

	printf("%d\n",cnt);

	for(int i=1;i<=n;++i) {

		for(int j=i+1;j<=n;++j) {

			if(j!=n-i+(n+1)%2) {

				printf("%d %d\n",i,j);

			}

		}

	}

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;



int main() {

    int n;

    cin >> n;





    if (n%2) {

        cout << (n*(n-1))/2 - n/2 << "\n";

        for (int i = 1; i <= n; i++) {

            for (int j = i+1; j <= n; j++) {

                if (i+j==n) continue;

                cout << i << " " << j << "\n";

            }

        }



    } else {

        cout << n*(n-2)/2 << "\n";

        for (int i = 1; i <= n; i++) {

            for (int j = i+1; j <= n; j++) {

                if (i+j==n+1) continue;

                cout << i << " " << j << "\n";

            }

        }

    }





    return 0;

}


// Optimized solution to the same problem (faster):
#include <cstdio>

#include <algorithm>

int doing(int n) {

	

}

int main() {

	int n;

	scanf("%d",&n);

	int cnt=0;

	for(int i=1;i<=n;++i) {

		for(int j=i+1;j<=n;++j) {

			if(j!=n-i+(n+1)%2) {

				++cnt;

			}

		}

	}

	printf("%d\n",cnt);

	for(int i=1;i<=n;++i) {

		for(int j=i+1;j<=n;++j) {

			if(j!=n-i+(n+1)%2) {

				printf("%d %d\n",i,j);

			}

		}

	}

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

#define Maxn 10007

int m,a[Maxn],b[Maxn],c[Maxn];

int n;

int main()

{

    scanf("%d",&n);

    if (n%2==0)

    {

        for (int i=1;i<=n/2;i++)

            c[i]=i,c[n+1-i]=i;

    } else

    {

        for (int i=1;i<=n/2;i++)

            c[i]=i,c[n-i]=i;

        c[n]=n;

    }

    for (int i=1;i<=n;i++)

        for (int j=i+1;j<=n;j++)

            if (c[i]!=c[j])

            {

                ++m;

                a[m]=i;

                b[m]=j;

            }

    printf("%d\n",m);

    for (int i=1;i<=m;i++)

        printf("%d %d\n",a[i],b[i]);

    return 0;

}

// Optimized solution to the same problem (faster):
#include <cstdio>

#include <algorithm>

int doing(int n) {

	

}

int main() {

	int n;

	scanf("%d",&n);

	int cnt=0;

	for(int i=1;i<=n;++i) {

		for(int j=i+1;j<=n;++j) {

			if(j!=n-i+(n+1)%2) {

				++cnt;

			}

		}

	}

	printf("%d\n",cnt);

	for(int i=1;i<=n;++i) {

		for(int j=i+1;j<=n;++j) {

			if(j!=n-i+(n+1)%2) {

				printf("%d %d\n",i,j);

			}

		}

	}

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

#define pb push_back

#define mp make_pair

#define pii pair <int, int>

#define fi first

#define sc second

#define ALL(x) x.begin(), x.end()

#define RALL(X) x.begin(), x.end()

#define FOR(i, n, k) for(i=0; i<n; i+=k)

#define FO(i, n, k) for(i=1; i<=n; i+=k)

#define CLEAR(a, b) memset(a, b, sizeof(a))

#define N 100005

#define mid ((l+r)/2)

#define dbg(x) (cerr << #x << " : " << x << endl)

#define endl "\n"

#define MOD 100000009



using namespace std;



typedef long long int lli;



const int NMAX = 1e2 + 5;



vector <pii> res;



int main(){

	ios_base::sync_with_stdio(false);

	int n;

	cin >> n;



	if(n%2 == 0){

		for(int i=1; i<=n; i++){

			for(int j=i+1; j<=n; j++){

				if(j != n-i+1){

					res.pb(mp(i, j));

				}

			}

		}

	}else{

		n--;

		for(int i=1; i<=n; i++){

			for(int j=i+1; j<=n; j++){

				if(j != n-i+1){

					res.pb(mp(i, j));

				}

			}

		}

		n++;

		for(int i=1; i<n; i++)

			res.pb(mp(i, n));

	}



	cout << res.size() << endl;

	for(pii r: res) {

		cout << r.fi << " " << r.sc << endl;

	}



	return 0;

}

// Optimized solution to the same problem (faster):
#include <cstdio>

#include <cstring>

bool matrix[105][105];

int arr[105];

int brr[105];

int N;

int main() {

    scanf("%d",&N);

    memset(matrix, true, sizeof(matrix));

    int sum = (N*(N+1)) / 2;

    int base, e;

    printf("%d\n",N*(N-1)/2 - N/2);

    if (N % 2) {

        base = N;

        e = N - 1;

    } else {

        base = N + 1;

        e = N;

    }



    for (int i = 1; i <= e; i++) {

        matrix[i][base - i] = matrix[base - i][i] = false;

    }

     for (int i = 1; i <= N; i++) {

        for (int j = 1; j <= N; j++) {

            if (i == j || !matrix[i][j])

                continue;

            printf("%d %d\n",i, j);

            matrix[i][j] = matrix[j][i] = false;

        }

    }

    return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

#define rep(i,n) for(int i=0;i<n;++i)

typedef long long ll;

struct edge{int to;ll cost;};

vector<edge> G[60000];

ll dp[60000];

priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> qu;//dp[],2*(n-1)*c+v



int a,b,c;

int nextv(int v){ return (a*v+b)%c;}



int main(void){

	int n,m,v0;

	cin>>n>>m;

	vector<int> x(m),y(m);

	vector<ll> t(m); 

	rep(i,m){

		cin>>x[i]>>y[i]>>t[i];

		--x[i];

		--y[i];

	}

	cin>>v0>>a>>b>>c;

	rep(i,m)rep(v,c){

		G[x[i]*c+v].push_back({y[i]*c+nextv(v),t[i]*v});

		G[y[i]*c+v].push_back({x[i]*c+nextv(v),t[i]*v});	

		G[((n-1)*2-x[i])*c+v].push_back({((n-1)*2-y[i])*c+nextv(v),t[i]*v});

		G[((n-1)*2-y[i])*c+v].push_back({((n-1)*2-x[i])*c+nextv(v),t[i]*v});

	}

	rep(i,60000)dp[i]=LLONG_MAX;

	dp[v0]=0;

	qu.push({0,v0});

	while(qu.size()){

		pair<ll,int> u = qu.top();

		qu.pop();

		if(u.second/c==2*(n-1)){

			cout<<dp[u.second]<<endl;

			return 0;			

		}

		if(dp[u.second] < u.first)continue;

		for(auto e:G[u.second]){

			if(dp[e.to] > dp[u.second] + e.cost){

				dp[e.to] = dp[u.second] + e.cost;

				qu.push({dp[e.to],e.to});

			}

		}



	}

	

	// ll res = LLONG_MAX;

	// rep(i,c){

	// 	res = min(res,dp[2*(n-1)*c+i]);

	// }

	// cout<<res<<endl;



	return 0;

}

// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;

#define rep(i,n) for(int i=0;i<n;++i)

typedef long long ll;

struct Trio{

	int to,v;

	ll cost;

	bool operator<(const Trio& right)const{

		return (cost > right.cost);

	}

};



int main(void){

	int n,m,v0,a,b,c;

	cin>>n>>m;

	vector<int> x(m),y(m);

	vector<ll> t(m);

	rep(i,m) cin>>x[i]>>y[i]>>t[i];

	cin>>v0>>a>>b>>c;

	vector<Trio> G[(n+1)*2][c];

	ll dp[(n+1)*2][c];

	rep(i,m)rep(v,c){

		int nextv=(a*v+b)%c;

		ll cost=t[i]*v;

		G[x[i]][v].push_back({y[i],nextv,cost});

		G[y[i]][v].push_back({x[i],nextv,cost});

		G[n+x[i]][v].push_back({n+y[i],nextv,cost});

		G[n+y[i]][v].push_back({n+x[i],nextv,cost});

	}

	rep(v,c) G[n][v].push_back({n*2,v,0});



	rep(i,(n+1)*2)rep(v,c) dp[i][v]=LLONG_MAX;

	dp[1][v0]=0;

	priority_queue<Trio,vector<Trio>> qu;

	qu.push({1,v0,0});

	while(qu.size()){

		Trio u=qu.top(); qu.pop();

		if(u.to==n+1){

			cout<<dp[u.to][u.v]<<endl;

			return 0;

		}

		if(dp[u.to][u.v] < u.cost)continue;

		for(auto e:G[u.to][u.v]){

			if(dp[e.to][e.v] > dp[u.to][u.v] + e.cost){

				dp[e.to][e.v] = dp[u.to][u.v] + e.cost;

				qu.push({e.to,e.v,dp[e.to][e.v]});

			}

		}

	}

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

#define ALL(v) v.begin(), v.end()

typedef long long ll;



#include <bits/stdc++.h>

using namespace std;



ll floor_sum(ll n,ll m,ll a,ll b){

  ll ans=0;

  ans+=(n-1)*n*(a/m)/2+n*(b/m);

  a%=m;

  b%=m;



  ll y_max=(a*n+b)/m, x_max=(y_max*m-b);

  if(y_max==0) return ans;

  ans+=(n-(x_max+a-1)/a)*y_max;

  ans+=floor_sum(y_max,a,m,(a-x_max%a)%a);

  return ans;

}



int main(){

  int t;

  cin>>t;

  

  rep(i,t){

    int n,m,a,b;

    cin>>n>>m>>a>>b;  

    cout<<floor_sum(n,m,a,b)<<endl;

  }

  

  return 0;

}

// Optimized solution to the same problem (faster):
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

#define ALL(v) v.begin(), v.end()

typedef long long ll;



#include <stdio.h>

using namespace std;



ll floor_sum(ll n,ll m,ll a,ll b){

  ll ans=0;

  if(a>=m){

    ans+=(n-1)*n*(a/m)/2;

    a%=m;

  }

  if(b>=m){

    ans+=n*(b/m);

    b%=m;

  }



  ll y_max=(a*n+b)/m;

  if(y_max==0) return ans;

  ans+=floor_sum(y_max,a,m,a*n-y_max*m+b);

  return ans;

}



int main(){

  int t;

  scanf("%d",&t);

  

  while(t--){

    int n,m,a,b;

    scanf("%d%d%d%d",&n,&m,&a,&b);

    printf("%lld\n",floor_sum(n,m,a,b));

  }

  

  return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

#define ALL(v) v.begin(), v.end()

typedef long long ll;



#include <bits/stdc++.h>

using namespace std;



ll floor_sum(ll n,ll m,ll a,ll b){

  ll ans=0;

  ans+=(n-1)*n*(a/m)/2+n*(b/m);

  a%=m;

  b%=m;



  ll y=(a*n+b)/m;

  if(y==0) return ans;

  ll x=(m*y-b+a-1)/a;

  ans+=(n-x)*y+floor_sum(y,a,m,a*x-m*y+b);

  return ans;

}



int main(){

  int t;

  cin>>t;

  

  rep(i,t){

    int n,m,a,b;

    cin>>n>>m>>a>>b;

  

    cout<<floor_sum(n,m,a,b)<<endl;

  }

  

  return 0;

}

// Optimized solution to the same problem (faster):
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

#define ALL(v) v.begin(), v.end()

typedef long long ll;



#include <stdio.h>

using namespace std;



ll floor_sum(ll n,ll m,ll a,ll b){

  ll ans=0;

  if(a>=m){

    ans+=(n-1)*n*(a/m)/2;

    a%=m;

  }

  if(b>=m){

    ans+=n*(b/m);

    b%=m;

  }



  ll y_max=(a*n+b)/m;

  if(y_max==0) return ans;

  ans+=floor_sum(y_max,a,m,a*n-y_max*m+b);

  return ans;

}



int main(){

  int t;

  scanf("%d",&t);

  

  while(t--){

    int n,m,a,b;

    scanf("%d%d%d%d",&n,&m,&a,&b);

    printf("%lld\n",floor_sum(n,m,a,b));

  }

  

  return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

#define ALL(v) v.begin(), v.end()

typedef long long ll;



#include <bits/stdc++.h>

using namespace std;



ll floor_sum(ll n,ll m,ll a,ll b){

  ll ans=0;

  if(a>=m){

    ans+=(n-1)*n*(a/m)/2;

    a%=m;

  }

  if(b>=m){

    ans+=n*(b/m);

    b%=m;

  }



  ll y=(a*n+b)/m;

  if(y==0) return ans;

  ll x=(m*y-b+a-1)/a;

  ans+=(n-x)*y+floor_sum(y,a,m,a*x-m*y+b);

  return ans;

}



int main(){

  int t;

  cin>>t;

  

  rep(i,t){

    int n,m,a,b;

    cin>>n>>m>>a>>b;

  

    cout<<floor_sum(n,m,a,b)<<endl;

  }

  

  return 0;

}

// Optimized solution to the same problem (faster):
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

#define ALL(v) v.begin(), v.end()

typedef long long ll;



#include <stdio.h>

using namespace std;



ll floor_sum(ll n,ll m,ll a,ll b){

  ll ans=0;

  if(a>=m){

    ans+=(n-1)*n*(a/m)/2;

    a%=m;

  }

  if(b>=m){

    ans+=n*(b/m);

    b%=m;

  }



  ll y_max=(a*n+b)/m;

  if(y_max==0) return ans;

  ans+=floor_sum(y_max,a,m,a*n-y_max*m+b);

  return ans;

}



int main(){

  int t;

  scanf("%d",&t);

  

  while(t--){

    int n,m,a,b;

    scanf("%d%d%d%d",&n,&m,&a,&b);

    printf("%lld\n",floor_sum(n,m,a,b));

  }

  

  return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

#define ALL(v) v.begin(), v.end()

typedef long long ll;



#include <bits/stdc++.h>

using namespace std;



ll floor_sum(ll n,ll m,ll a,ll b){

  ll ans=0;

  if(a>=m){

    ans+=(n-1)*n*(a/m)/2;

    a%=m;

  }

  if(b>=m){

    ans+=n*(b/m);

    b%=m;

  }



  ll y_max=(a*n+b)/m;

  if(y_max==0) return ans;

  ans+=floor_sum(y_max,a,m,a*n-y_max*m+b);

  return ans;

}



int main(){

  int t;

  cin>>t;

  

  rep(i,t){

    int n,m,a,b;

    cin>>n>>m>>a>>b;

  

    cout<<floor_sum(n,m,a,b)<<endl;

  }

  

  return 0;

}

// Optimized solution to the same problem (faster):
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

#define ALL(v) v.begin(), v.end()

typedef long long ll;



#include <stdio.h>

using namespace std;



ll floor_sum(ll n,ll m,ll a,ll b){

  ll ans=0;

  if(a>=m){

    ans+=(n-1)*n*(a/m)/2;

    a%=m;

  }

  if(b>=m){

    ans+=n*(b/m);

    b%=m;

  }



  ll y_max=(a*n+b)/m;

  if(y_max==0) return ans;

  ans+=floor_sum(y_max,a,m,a*n-y_max*m+b);

  return ans;

}



int main(){

  int t;

  scanf("%d",&t);

  

  while(t--){

    int n,m,a,b;

    scanf("%d%d%d%d",&n,&m,&a,&b);

    printf("%lld\n",floor_sum(n,m,a,b));

  }

  

  return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

#define ALL(v) v.begin(), v.end()

typedef long long ll;



#include <bits/stdc++.h>

using namespace std;



ll floor_sum(ll n,ll m,ll a,ll b){

  ll ans=0;

  if(a>=m){

    ans+=(n-1)*n*(a/m)/2;

    a%=m;

  }

  if(b>=m){

    ans+=n*(b/m);

    b%=m;

  }



  ll y_max=(a*n+b)/m;

  if(y_max==0) return ans;

  ans+=floor_sum(y_max,a,m,a*n-y_max*m+b);

  return ans;

}



int main(){

  int t;

  cin>>t;

  

  rep(i,t){

    int n,m,a,b;

    cin>>n>>m>>a>>b;

  

    cout<<floor_sum(n,m,a,b)<<'\n';

  }

  

  return 0;

}

// Optimized solution to the same problem (faster):
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

#define ALL(v) v.begin(), v.end()

typedef long long ll;



#include <stdio.h>

using namespace std;



ll floor_sum(ll n,ll m,ll a,ll b){

  ll ans=0;

  if(a>=m){

    ans+=(n-1)*n*(a/m)/2;

    a%=m;

  }

  if(b>=m){

    ans+=n*(b/m);

    b%=m;

  }



  ll y_max=(a*n+b)/m;

  if(y_max==0) return ans;

  ans+=floor_sum(y_max,a,m,a*n-y_max*m+b);

  return ans;

}



int main(){

  int t;

  scanf("%d",&t);

  

  while(t--){

    int n,m,a,b;

    scanf("%d%d%d%d",&n,&m,&a,&b);

    printf("%lld\n",floor_sum(n,m,a,b));

  }

  

  return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

const int N=510;

struct dat{

    int x,y,id;

    dat(){}

    dat(int x,int y,int id):

        x(x),y(y),id(id){}

}a[N];

int n,mod,cnt=0;

long long ans=0ll;

long long f[N][N];

inline bool cmp(dat x,dat y)

{

    if(x.x^y.x) return x.x<y.x;

    else return x.y<y.y;

}

inline long long add(long long x,long long y)

{

    return x+y>=mod?x+y-mod:x+y;

}

inline long long sub(long long x,long long y)

{

    return x-y<0?x-y+mod:x-y;

}

int main()

{

//    freopen("1.in","r",stdin);

    scanf("%d%d",&n,&mod);

    for(int k=0;k<2*n;k++)

    {

        int l=max(0,(int)ceil(sqrt(n*n-k*k))),r=min(2*n-1,(int)sqrt(n*n*4-k*k));

        if(k<n) a[++cnt]=dat(l-1,r,k);

        else a[++cnt]=dat(r,0,k);

    }

    sort(a+1,a+1+cnt,cmp);

    for(int k=0;k<=n;k++)

    {

        memset(f,0,sizeof f);

        f[0][0]=1ll;

        int x=0;

        for(int i=1;i<=cnt;i++)

        {

            for(int j=0;j<=k;j++)

            {

                if(a[i].id<n)

                {

                    if(a[i].x+1-x-(j-1)>0&&j)

                        f[i][j]=add(f[i][j],f[i-1][j-1]*(a[i].x+1-x-(j-1))%mod);

                    if(a[i].y+1-k-n-(i-1-x-j)>0)

                        f[i][j]=add(f[i][j],f[i-1][j]*(a[i].y+1-k-n-(i-1-x-j))%mod);

                }

                else

                {

                    if(a[i].x+1-x-j>0)

                        f[i][j]=f[i-1][j]*(a[i].x+1-x-j)%mod;

                }

            }

            if(a[i].id>=n) x++;

        }

        if(k&1) ans=sub(ans,f[cnt][k]);

        else ans=add(ans,f[cnt][k]);

    }

    printf("%lld\n",ans);

    return 0;

}


// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>

#define maxn 605

#define rep(i,j,k) for(int i=(j),LIM=(k);i<=LIM;i++)

#define per(i,j,k) for(int i=(j),LIM=(k);i>=LIM;i--)

#define LL long long

using namespace std;



int n;

int mod;

int f[2][maxn];

int up[maxn],dn[maxn],d[maxn],c[maxn];

bool cmp(const int &u,const int &v){ return d[u] < d[v]; }



int main(){

	scanf("%d%d",&n,&mod);

	rep(i,0,2*n-1) up[i] = min((int)floor(sqrt(4 * n * n - i * i)),2*n-1) , dn[i] = (i <= n ? (int)ceil(sqrt(n * n - i * i)) : 0);

	rep(i,0,n-1) d[i] = dn[i] - 1;

	rep(i,n,2*n-1) d[i] = up[i];

	rep(i,0,2*n-1) c[i] = 2*n-i-1;

	stable_sort(c,c+2*n,cmp);int ans =0 ;

	rep(k,0,n){

		memset(f,0,sizeof f);

		int now = 1, pre = 0 , cntr = 0;

		f[now][0] = 1;

		rep(i,0,2*n-1){

			int u = c[i];

			swap(now,pre);

			rep(j,0,k) if(f[pre][j]){

				if(u >= n){	

					f[now][j] = (f[now][j] + 1ll * f[pre][j] * max(up[u] + 1 - i + (cntr - j), 0)) % mod;

				}

				else{

					f[now][j] = (f[now][j] + 1ll * f[pre][j] * max(up[u] + 1 - n - (k-j) - cntr , 0)) % mod;

					if(j < k) f[now][j+1] = (f[now][j+1] + 1ll * f[pre][j] * max(dn[u] - i + (cntr - j) , 0)) % mod;

				}

				f[pre][j] = 0;

			}

			if(u < n) cntr ++;

		}

		ans = (ans + (k&1?-1ll:1ll) * f[now][k]) % mod;

	}

	printf("%d\n",(ans+mod)%mod);

}

// Fastest known solution for this problem: