艾丽丝看着星星,脑海中浮现出一个美丽的问题。她邀请你解决这个问题,以便相信流星雨的形成。
天空中有 $$$n$$$ 颗星星,排列成一排。艾里斯有一架望远镜,她用它来观察星星。
最初,Iris 观察了 $$$[1, n]$$$ 段中的星星,她的幸运值为 $$$0$$$。 Iris 想要为她观察到的每个段 $$$[l, r]$$$ 寻找中间位置的星星。因此使用以下递归过程:
- 首先,她将计算 $$$m = \left\lfloor \frac{l+r}{2} \right\rfloor$$$。
- 如果该段的长度(即 $$$r - l + 1$$$)是偶数,Iris 会将其分为两个等长的段 $$$[l, m]$$$ 和 $$$[m+1, r]$$$ 以便进一步观察。
- 否则,Iris会将望远镜瞄准恒星$$$m$$$,她的幸运值将增加$$$m$$$;随后,如果 $$$l \neq r$$$,Iris 将继续观察两个段 $$$[l, m-1]$$$ 和 $$$[m+1, r]$$$。
Iris 有点懒。她用整数 $$$k$$$ 定义自己的懒惰:随着观察的进行,她将不会继续观察长度严格小于 $$$k$$$ 的任何段 $$$[l, r]$$$。在这种情况下,请预测她最终的幸运值。
输入
每个测试包含多个测试用例。输入的第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的唯一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \leq k \leq n \leq 2\cdot 10^9$$$)。
输出
对于每个测试用例,输出一个整数——最终的幸运值。
示例
输入 #1
6 7 2 11 3 55 13 5801 6 8919 64 8765432 1
输出 #1
12 18 196 1975581 958900 38416403456028
注意
在第一个测试用例中,一开始,Iris 观察到 $$$[1, 7]$$$。由于 $$$[1, 7]$$$ 的长度为奇数,她的目标是星星 $$$4$$$,因此她的幸运值增加了 $$$4$$$。然后它被分成 $$$2$$$ 新段:$$$[1, 3]$$$ 和 $$$[5, 7]$$$。 $$$[1, 3]$$$ 段的长度再次为奇数,因此 Iris 瞄准星星 $$$2$$$ 并将她的幸运值增加 $$$2$$$。然后将其分割成$$$2$$$新段:$$$[1, 1]$$$和$$$[3, 3]$$$,两者的长度均小于$$$2$$$,因此不再进行进一步观察。对于范围 $$$[5, 7]$$$,进度类似,幸运值最终增加 $$$6$$$。因此,最终的幸运值为$$$4 + 2 + 6 = 12$$$。
在最后一个测试用例中,Iris 最终观察到了所有星星,最终的幸运值是 $$$1 + 2 + \cdots + 8\,765\,432 = 38\,416\,403\,456\,028$$$。