C. Очаровательный звездочет
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
I'm praying for owning a transparent heart; as well as eyes with tears more than enough...
— Escape Plan, Brightest Star in the Dark

Ирис посмотрела на звезды, и в её голове возникла прекрасная задача. Она приглашает вас решить её, чтобы можно было предсказать метеоритный дождь.

На небе есть $$$n$$$ звезд, расположенных в ряд. У Ирис есть телескоп, с помощью которого она смотрит на них.

Изначально Ирис наблюдает за звездами в отрезке $$$[1, n]$$$, и у неё есть значение удачи, равное $$$0$$$. Ирис хочет найти центральную звезду для каждого отрезка $$$[l, r]$$$, за которым она наблюдает. Она использует следующую рекурсивную процедуру:

  • Сначала она вычисляет $$$m = \left\lfloor \frac{l+r}{2} \right\rfloor$$$.
  • Если длина отрезка (т.е. $$$r - l + 1$$$) чётная, Ирис разделяет его на два отрезка одинаковой длины $$$[l, m]$$$ и $$$[m+1, r]$$$ для дальнейшего наблюдения.
  • В противном случае Ирис наведёт телескоп на звезду $$$m$$$, и её значение удачи увеличится на $$$m$$$; далее, если $$$l \neq r$$$, Ирис продолжит наблюдать за двумя отрезками $$$[l, m-1]$$$ и $$$[m+1, r]$$$.

Ирис немного ленива. Она определяет свою лень целым числом $$$k$$$: по мере продвижения наблюдения она не станет наблюдать за отрезком $$$[l, r]$$$, если его длина строго меньше $$$k$$$. Пожалуйста, предскажите её итоговое значение удачи.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Единственная строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \leq k \leq n \leq 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]$$$. Поскольку у $$$[1, 7]$$$ нечётная длина, она наводит телескоп на звезду $$$4$$$ и, следовательно, увеличивает своё значение удачи на $$$4$$$. Затем отрезок разбивается на $$$2$$$ новых отрезка: $$$[1, 3]$$$ и $$$[5, 7]$$$. Отрезок $$$[1, 3]$$$ снова имеет нечётную длину, поэтому Ирис прицеливается на звезду $$$2$$$ и увеличивает своё значение удачи на $$$2$$$. Затем он разбивается на $$$2$$$ новых отрезка: $$$[1, 1]$$$ и $$$[3, 3]$$$, оба из которых имеют длину меньше $$$2$$$, поэтому дальнейшее наблюдение не проводится. Что касается отрезка $$$[5, 7]$$$, то прогресс аналогичен, и значение удачи увеличивается на $$$6$$$. Следовательно, итоговое значение удачи равняется $$$4 + 2 + 6 = 12$$$.

В последнем наборе входных данных, Ирис в итоге понаблюдает за всеми звёздами, и итоговым значением удачи будет $$$1 + 2 + \cdots + 8\,765\,432 = 38\,416\,403\,456\,028$$$.