#4882. [Lydsy1705月赛]卡常生成树

题目描述

小Q最近沉迷底层优化，他终于将他的MST模板优化到了很可怕的地步，所以他出了这道题来试验模板的速度。给定

一个n个点的带权无向连通图，点的编号从1到n，请求出这个图的最小生成树。为了避免输入数据过于庞大，数据

进行了压缩，解压方式可用下面这段代码解释：

void encode(int seed, int n){

int x = seed;

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

    x = x * 907 % 2333333;

    int T = x;

    for(int j = max(1, i - 5); j <= i - 1; j++){

        x = x * 907 % 2333333;

        int w = T ^ x;

        add_edge(i, j, w);//在点i与点j之间添加一条边权为w的边

    }

}

}

输入格式

第一行包含一个正整数T(1<=T<=50)，表示测试数据的组数。

每组数据只包含一行两个正整数n,seed(1<=n<=10^7,1<=seed<=2333332)，含义如题面所述。

输出格式

对于每组数据，输出一行一个整数，即最小生成树的树边的权值之和。

样例

样例输入

3  

3010 2016  

3 14159  

31415 926

样例输出

750887251  

3382896  

9210525875

数据范围与提示