题目描述
T
协会的主席大 G
决定选出一位小 g
继任 T
协会的主席之位。为了保证公平性,他任命小 c
担任监督。
考虑到 T
协会的小 g
们不是很多,小 c
决定通过最简单的方式决出胜者:让这 n 个小 g
两两进行一场没有平局的对决,胜者获得一分,败者则不获得的分数。
在比赛结束、统计分数的时候,小 c
发现了关于本次 n(n−1)2 场对决的 “z-gg
定律”,即在任意 z+1 个小 g
中,总存在一个小 g
能打败其余 z 个小 g
,同时存在另一个小 g
被其余 z 个小 g
打败。
由于某些来自 T
协会的神秘因素,小 c
突然想知道在所有符合上述 “z-gg
定律” 的对决中,n 个小 g
最少有多少种不同的得分?由于小 c
忙(bu)于(shi)统(te)计(bie)数(cong)据(ming),所以她决定将这个问题交给你来回答。
输入格式
从标准输入读入数据。
本题有多组数据。
第一行包含一个整数 T(1≤T≤3×105) 表示数据组数。
接下来 T 行,每行两个正整数 n,z(1≤z<n≤1018) 如题面所述。
输出格式
输出到标准输出。
T 行,每行一个正整数表示答案。
样例
输入
5
2 1
3 1
3 2
4 1
4 3
输出
2
1
3
2
4
解释
对 n=2,z=1,显然此时两个小 g
得分必然一个是 1,另一个是 0,故答案为 2。
对 n=3,z=1,1=>2, 2=>3, 3=>1
(a=>b
表示 “a 打败 b”,下同)满足定律,且每个人得分均为 1 分;
对 n=3,z=2,由对称性以及题设定律,不妨设 1
和 3
是 3 个小 g
中的全胜和全败者,那么这场比赛必定为 1=>2, 1=>3, 2=>3
,此时三人得分依次为 2,1,0,故答案为 3。
对 n=4,z=1,1=>3, 1=>4, 2=>1, 2=>3, 3=>4, 4=>2
中四人得分依次为 2,2,1,1,并且由于四人得分之和 4×32=6 不是 4 的倍数,故四人得分不可能完全一致,故答案为 2。
对 n=4,z=3,仍设四人中全胜和全败者为 1
和 4
,则此时 2
、3
两人得分之和为 6−3−0=3,因此二者得分只能为 2,1 或者 3,0;又显然不可能同时有两个得分为 3 分者,故此时 2
和 3
的得分必为 2,1,故答案为 4。
样例
输入
6
7 1
7 2
7 3
7 4
7 5
7 6
输出
1
7
7
7
5
3
提示
本题并不难。