有一个圆形的停车场,里面有n个停车位。停车位的编号从0至n-1,因为停车场是圆形的,所以第n-1个停车位的下一个停车位就是第0个停车位。
一开始所有停车位都是空的。现在有n台汽车排队进来停车,只有前面进去的车已经停好位置了,那么下一台汽车才能进入停车场。
n台汽车的编号是从0至n-1, 注意:汽车的编号与停车位的编号不是直接对应关系,第i台汽车不一定停在第i个停车位。
确切一点说,第i台汽车最喜欢停在第p[i]个停车位,但是如果在它前面进场的汽车已经把该停车位占据了,
那么第i台汽车就会从第p[i]+1个停车位开始往后搜索,一旦找到一个空的停车位,第i台汽车就停在那个空的停车位。
容易发现,一台汽车在找到合适的停车位之前,可能出现多次“冲突”。
例如第i台汽车最喜欢停在第p[i]个停车位,但是第p[i]个停车位被占了,那么就“冲突”1次,
然后第i台汽车就想停在第p[i]+1个停车位,如果第p[i]+1个停车位也被占了,那么又多了1次“冲突”,......
问当所有的汽车都停车结束以后,停车过程中,总共产生了多少次冲突?
多组测试数据。
第一行,一个整数G,表示有G组测试数据。1<=G<=10。
每组测试数据格式如下:
一行,4个整数:n,A,B,C。1<=n<=250000。0 <= A,B,C < n。
其中A,B,C三个整数的作用是用来产出p[i]的。
P[i] = (A*i*i + B*i + C) % n, 其中 0<=i<n。
共G行,每行一个整数。
输入:
5
47 0 1 0
47 0 0 42
30 1 1 1
250000 2352 32652 199975
250000 0 0 248987
输出:
0
1081
175
93375000
31249875000
5
47 0 1 0
47 0 0 42
30 1 1 1
250000 2352 32652 199975
250000 0 0 248987
0
1081
175
93375000
31249875000