第五集：跳跳跳跳

"啊哈哈哈哈，赚了这么多天鹅肉，够本大仙吃一整子了！小伙子不错！"

"这下你满意了吧，快带我去小C那儿吧！" 小A迫不及待的说到

"emmmmm，还有一个小小的问题" 小晋抖着二郎腿，嘴里吃了天鹅肉，含混不清的说到

"!!!!,你个#￥@￥，又说话不算话，我和你拼了" 小A边说边撸袖子

"别别别，君子动口不动手，且听我细细道来，是这样的：你和小C之间呢，有一条笔直的通道，一条线懂吗？"

"懂？我懂你个头，你最好说快点，不然我可动手了！" 小A见势就要上去干

"

这条通道上会有很多的跳板，分别在点a0,a1,a2....a_n-1，当然，我们现在在最小（MIN ai）的跳板上，小C当然就在最大(MAX ai)的跳板上，最遥远的距离~~

但是！这个转折就问你怕不怕！每个跳板出现的位置，是由下面这段代码决定的，你帮我算算，我最少要能跳多远才能通过跳板跳到小C那边

void xiaojin666(int n,int A,int B,int C){

    unsigned x = A, y = B, z = C;

    unsigned t;

    for(int i=0;i<n;++i){

        x ^= x << 16;

        x ^= x >> 5;

        x ^= x << 1;

        t = x;

        x = y;

        y = z;

        z = t ^ x ^ y;

        a[i] = z;

    }

    for(int i=0;i<n;++i){

        if(a[i] < 0)

            a[i] = -a[i];

    }

}

当然，我只记得n,A,B,C哈

"

假设生成的数组是1 5 3 4，那么起点是1，终点是5，跳跃方式是1-3-4-5，答案是2

第一行一个整数t，代表数据组数.
接下来有t组数据，每组数据只包含4个整数，n,A,B,C
其中A,B,C为数列的生成参数，再通过上文中的代码（xiaojin666）生成n个数
0<A,B,C<=107
2<=n<=107
Σn<=5*107

输出一个整数，代表小晋最少要能跳多远才能从起点跳到终点

2
2 1 1 1
10000000 2 3 3

202754
3859