#3866. [Hnoi2010]Fsk物品调度

[Hnoi2010]Fsk物品调度

Background

Special for beginners, ^_^

Description

现在找工作不容易,Lostmonkey费了好大劲才得到fsk公司基层流水线操作员的职位。流水线上有n个位置,从0到n-1依次编号,一开始0号位置空,其它的位置i上有编号为i的盒子。Lostmonkey要按照以下规则重新排列这些盒子。 规则由5个数描述,q,p,m,d,s,s表示空位的最终位置。首先生成一个序列c,c0=0,ci+1=(ciq+p) mod m。接下来从第一个盒子开始依次生成每个盒子的最终位置posi,posi=(ci+dxi+yi) mod n,xi,yi是为了让第i个盒子不与之前的盒子位置相同的由你设定的非负整数,且posi还不能为s。如果有多个xi,yi满足要求,你需要选择yi最小的,当yi相同时选择xi最小的。 这样你得到了所有盒子的最终位置,现在你每次可以把某个盒子移动到空位上,移动后原盒子所在的位置成为空位。请问把所有的盒子移动到目的位置所需的最少步数。

Format

Input

Two integers x and y, satisfying 0x,y327670\leq x,y\leq 32767 .

Output

第一行包含一个整数t,表示数据组数。接下来t行,每行6个数,n,s,q,p,m,d意义如上所述。 对于30%的数据n<=100,对于100%的数据t<=20,n<=100000,sOutput对于每组数据输出一个数占一行,表示最少移动步数。

Samples

1
8 3 5 2 7 4
6

Limitation

说明:第1个到第7个盒子的最终位置依次是:2 5 6 4 1 0 7 计算过程可能超过整型范围。