C++ :

#include <bits/stdc++.h>
using namespace std;
long long t[500005];
long long dp[500005];
const long long MOD = 2147483648;
int main()
{
	int g;
	cin >> g;
	deque<int> deq;
	while (g--) {
		int n, l;
		long long seed, m;
		cin >> n >> l >> seed >> m;
		t[0] = 0;
		long long state = seed; 
		for (int i = 1; i <= n; i++) {
			state = (state * 1103515245 + 12345) % MOD;
			t[i] = 1 + (state % m);
		}
		dp[0] = 0;
		deq.push_back(0);
		for (int i = 1; i <= n; i++) {
			while (!deq.empty() && deq.front() < i-l)
				deq.pop_front();
			dp[i] = dp[deq.front()]+t[i];
			while (!deq.empty() && dp[deq.back()] > dp[i])
				deq.pop_back();
			deq.push_back(i);
		}
		cout << dp[n] << endl;
		while (!deq.empty()) deq.pop_back();
	}
	return 0;
}