C. 迷人的占星师

每个测试用例的时间限制：$2$ 秒 每个测试用例的内存限制：$256$ 兆字节

我祈求拥有一颗透明的心灵，和一双会流泪的眼睛…… —— 逃跑计划《夜空中最亮的星》

艾瑞斯望着星空，脑海中浮现出一道美妙的题目。她邀请你来解答，据说这样就能迎来一场流星雨。

天空中有 $n$ 颗星星，排成一排。艾瑞斯有一台望远镜，用来观测这些星星。

初始时，艾瑞斯观测的区间是 $[1,n]$，她的幸运值为 $0$。 对于每一个她观测的区间 $[l,r]$，艾瑞斯都会寻找中间位置的星星，观测规则如下：

1. 首先计算 $m = \lfloor \frac{l+r}{2} \rfloor$。
2. 如果区间长度（即 $r-l+1$）为偶数，艾瑞斯会将其分成两个等长的子区间 $[l,m]$ 和 $[m+1,r]$ 继续观测。
3. 如果区间长度为奇数：
   • 艾瑞斯会将望远镜对准第 $m$ 颗星星，幸运值增加 $m$；
   • 若 $l \neq r$，艾瑞斯会继续观测两个子区间 $[l,m-1]$ 和 $[m+1,r]$。

艾瑞斯有点懒，她用一个整数 $k$ 定义自己的懒惰程度：在观测过程中，不会继续观测长度严格小于 $k$ 的区间 $[l,r]$。

请你计算她最终的幸运值。

输入

输入包含多个测试用例。 第一行输入一个整数 $t$（$1 \le t \le 10^5$）—— 测试用例的数量。 每个测试用例仅有一行，包含两个整数 $n$ 和 $k$（$1 \le k \le n \le 2 \cdot 10^9$）。

输出

对于每个测试用例，输出一个整数 —— 最终的幸运值。

样例输入

6
7 2
11 3
55 13
5801 6
8919 64
8765432 1

样例输出

12
18
196
1975581
958900
38416403456028

样例说明

第一个测试用例： 初始观测区间 $[1,7]$，长度为奇数，对准第 $4$ 颗星星，幸运值 $+4$；随后分成两个子区间 $[1,3]$ 和 $[5,7]$。 区间 $[1,3]$ 长度为奇数，对准第 $2$ 颗星星，幸运值 $+2$；随后分成 $[1,1]$ 和 $[3,3]$，两个区间长度都小于 $2$，停止观测。 区间 $[5,7]$ 同理，幸运值 $+6$。 最终幸运值为 $4+2+6=12$。

最后一个测试用例： 艾瑞斯观测了所有星星，最终幸运值为 $1+2+\dots+8765432 = 38416403456028$。