G. Симон и диофантово уравнение
ограничение по времени на тест
6 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

I walk alone, into distance, through the fading light, biding my time for the sunset's final light.
— SHUN, CHAKA

Симон дал вам два целых числа $$$n$$$ и $$$m$$$.

Посчитайте количество упорядоченных кортежей $$$(i, j, k)$$$, таких что:

  • $$$0\le i, j, k\le m$$$, и
  • Существуют два целых числа $$$x$$$ и $$$y$$$, такие что $$$(i \oplus j) \cdot x + (j \oplus k) \cdot y = n$$$, где $$$\oplus$$$ обозначает операцию побитового исключающего ИЛИ.
Входные данные

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

Единственная строка содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1\le n\le 10^9$$$, $$$1\le m\le 3\cdot 10^5$$$) — заданные целые числа.

Гарантируется, что сумма значений $$$m$$$ по всем наборам входных данных не превосходит $$$3\cdot10^5$$$.

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

Для каждого набора входных данных выведите одно целое число — количество упорядоченных кортежей $$$(i,j,k)$$$, которые удовлетворяют условию.

Пример
Входные данные
5
3 2
4 6
1 1
7 20
720 2025
Выходные данные
18
254
6
5558
7864357450
Примечание

В первом наборе входных данных есть $$$18$$$ кортежей, которые удовлетворяют условиям. Например:

  • $$$(2,1,2)$$$ является допустимым кортежем, потому что уравнение $$$(2\oplus 1)\cdot x+(1\oplus 2)\cdot y=3$$$ имеет целочисленное решение $$$x=3$$$, $$$y=-2$$$.
  • $$$(1,1,0)$$$ также является допустимым кортежем, потому что уравнение $$$(1\oplus 1)\cdot x+(1\oplus 0)\cdot y=3$$$ имеет целочисленное решение $$$x=100$$$, $$$y=3$$$.
  • $$$(2,0,2)$$$ не является допустимым кортежем, потому что уравнение $$$(2\oplus 0)\cdot x+(0\oplus 2)\cdot y=3$$$ не имеет целочисленного решения.
  • $$$(1,1,1)$$$ не является допустимым кортежем, потому что уравнение $$$(1\oplus 1)\cdot x+(1\oplus 1)\cdot y=3$$$ не имеет целочисленного решения.
  • $$$(3,2,1)$$$ не является допустимым кортежем, потому что $$$3 \gt 2$$$.