1281 : 循环赛

Description

T 协会的主席大 G 决定选出一位小 g 继任 T 协会的主席之位。为了保证公平性，他任命小 c 担任监督。

考虑到 T 协会的小 g 们不是很多，小 c 决定通过最简单的方式决出胜者：让这 \(n\) 个小 g 两两进行一场没有平局的对决，胜者获得一分，败者则不获得的分数。

在比赛结束、统计分数的时候，小 c 发现了关于本次 \(\frac{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)，所以她决定将这个问题交给你来回答。

Input

本题有多组数据。

第一行包含一个整数 \(T(1\le T\le 3\times 10^5)\) 表示数据组数。

接下来 \(T\) 行，每行两个正整数 \(n,z(1\le z<n\le 10^{18})\) 如题面所述。

Output

\(T\) 行，每行一个正整数表示答案。

Sample

5
2 1
3 1
3 2
4 1
4 3
##CASE##
6
7 1
7 2
7 3
7 4
7 5
7 6

2
1
3
2
4

##CASE##
1
7
7
7
5
3

Hint

对 \(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\)，并且由于四人得分之和 \(\frac{4\times 3}{2}=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\)。

本题并不难。

Source

Author

THU