QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB

# 8756. 循环赛

Statistics

题目描述

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),所以她决定将这个问题交给你来回答。

输入格式

从标准输入读入数据。

本题有多组数据。

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

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

输出格式

输出到标准输出。

$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=>1a=>b 表示 “a 打败 b”,下同)满足定律,且每个人得分均为 $1$ 分;

对 $n=3, z=2$,由对称性以及题设定律,不妨设 13 是 $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$,仍设四人中全胜和全败者为 14,则此时 23 两人得分之和为 $6 - 3 - 0 = 3$,因此二者得分只能为 $2, 1$ 或者 $3, 0$;又显然不可能同时有两个得分为 $3$ 分者,故此时 23 的得分必为 $2, 1$,故答案为 $4$。

样例

输入

6
7 1
7 2
7 3
7 4
7 5
7 6

输出

1
7
7
7
5
3

提示

本题并不难。