解题思路
把机位 1…N 按模 d 余数分组。余数 r 与 d−r 互补（含 0 与 d/2 的自配对），两编号之和能被 d 整除。
求最大无冲突集规模 α(N,d)，保底规模 K=α+1。
记 q=⌊N/d⌋，rem=Nmodd。余数 0 与（d 为偶数时的）d/2 最多各取 1 个；每一对互补余数 (r,d−r) 只能整组取较大的一侧。用区间并集计数求出“贡献为 q+1 的对数”W，即可 O(1) 算出 α。
复杂度分析
题目内容
机场有编号 1 到 N 的 N 个机位。运行手册规定：若选出的机位中存在两个编号之和能被班期模数 d 整除，则这两班会在滑行道上发生冲突。调度需要知道保底规模 K：最小的整数 K，使得无论怎样选出 K 个不同机位，都必然发生上述冲突。该阈值记为 K(N,d)。请对每组 N 与 d 求出这个保底规模。
约束：测试组数不超过 200000；每组满足 1<d<N≤1000000000000000000。
输入描述
第一行一个整数 T，表示测试组数。
接下来 T 行，每行两个整数 N 和 d。
保证 1≤T≤200000，1<d<N≤1000000000000000000。
输出描述
输出 T 行，每行一个整数，表示对应的 K(N,d)。
样例1
输入
4
5 2
8 4
9 5
15 4
输出
3
5
6
7
说明
按模 d 余数分组，最大无冲突集规模加 1 即为阈值 K。四组答案依次为 3、5、6、7。
样例2
输入
2
6 5
20 6
输出
5
11
说明
两组同样用余数互补对的计数公式：K(6,5)=‘5‘，$K(20,6)=11。
