有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行，每行一个整数。