解题思路

• 把 1…N 的数按模 d 的余数分组。若两张卡余数分别为 r 与 d−r（含 0 与 d/2 的自配对），它们之和能被 d 整除。

• 问题等价于：求一个最大规模的集合 α(N,d)，使得集合中任意两数之和都 不能 被 d 整除；则答案 K(N,d) = α(N,d) + 1（抽屉原理）。

• 记 q = ⌊N/d⌋，rem = N % d。在 1…N 中：

  • 余数为 0 的数有 q 个；
  • 余数为 1..rem 的每个余数组有 q+1 个；
  • 余数为 rem+1..d-1 的每个余数组有 q 个。

• 构造最大集合的规则（贪心/计数）：

题目内容

某超市举办“盲盒选品”活动，盲盒内装有编号 $1$ 到 $N$ 的 $N$ 个商品卡片。活动规则要求：若选到的卡片中存在两种编号之和能被 $d$ 整除，则可额外兑换一份礼品。

顾客希望知道“保底门槛”——即确定最小的选卡数量 $K$ ，使得无论顾客选择哪 $K$ 张不同的卡片，都必然存在两张卡片的编号之和能被 $d$ 整除（触发兑换条件）。这个“保底门槛” $K$ 就是需要计算的 $K(N,d)$ 。

输入描述

每个测试文件均包含多组测试数据，第一行输入一个整数 $T(1≤T≤2×10^5)$ 代表数据组数，每组测试数据描述如下：

接下来 $T$ 行，每行输入两个整数 $N,d(1＜d＜N≤10^{18})$ 。

输出描述

输出 $T$ 行，每行一个整数，表示答案 $K(N,d)$ 。

样例1

输入

3
7 3
10 2
10 3

输出

5
3
6