[Lydsy2017年5月月赛]卡常生成树

时间限制:5s      空间限制:256MB

题目描述

小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

提示

没有写明提示


题目来源

鸣谢Claris上传试题

Menuappsclose