【题目描述】

有n+1个箱子从左往右排成一行，编号从0至n 。一开始你在第0个箱子，你的目标是到达第n个箱子。你可以通过跳跃来完成目标，每一步你的跳跃距离不能超过L，你可以选择向左跳，也可以选择向右跳，你任何时刻都不能跳出边界。每当你落在第i个箱子上面，你会受到T[i]点伤害值。求为了完成任务，至少会受到多少伤害值。伤害值用如下的公式产生：

T[0] = 0
state = seed
for i = 1 to N:
    state = (state * 1103515245 + 12345) % 2^31
T[i] = 1 + (state % M)

【输入格式】

多组测试数据。

第一行，一个整数G,表示有G组测试数。1<=G<=3。

每组测试数据格式如下：

一行，4个整数：n, L, seed,M。

$1<=n<=500000，1<=L<=500000，0<=seed<2^{31}， 1<=M<=10^9$。

【输出格式】

共G行，每行一个整数。

【输入样例】

3
8 3 47 10
100 1 47 123456789
5 5 12345 54321

【输出样例】

17
5835166389
46038