C2. Shohag любит XOR (сложная версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Различия между двумя версиями выделены жирным шрифтом. Вы можете совершать взломы только в том случае, если решены обе версии задачи.

У Shohag есть два целых числа $$$x$$$ и $$$m$$$. Помогите ему подсчитать количество целых чисел $$$1 \le y \le m$$$ таких, что $$$x \oplus y$$$ делится$$$^{\text{∗}}$$$ либо на $$$x$$$, либо на $$$y$$$, либо сразу на оба числа. Здесь $$$\oplus$$$ обозначает операцию побитового исключающего ИЛИ.

$$$^{\text{∗}}$$$Число $$$a$$$ делится на число $$$b$$$, если существует целое число $$$c$$$ такое, что $$$a = b \cdot c$$$.

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

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

Первая и единственная строка каждого набора входных данных содержит два целых числа $$$x$$$ и $$$m$$$ ($$$1 \le x \le 10^6$$$, $$$1 \le m \le 10^{18}$$$).

Гарантируется, что сумма $$$x$$$ по всем наборам входных данных не превосходит $$$10^7$$$.

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

Для каждого набора входных данных выведите одно целое число — количество подходящих $$$y$$$.

Пример
Входные данные
5
7 10
2 3
6 4
1 6
4 1
Выходные данные
3
2
2
6
1
Примечание

В первом наборе входных данных для $$$x = 7$$$ существует $$$3$$$ допустимых значения $$$y$$$ среди целых чисел от $$$1$$$ до $$$m = 10$$$ — числа $$$1$$$, $$$7$$$ и $$$9$$$.

  • $$$y = 1$$$ подходит, потому что $$$x \oplus y = 7 \oplus 1 = 6$$$ и $$$6$$$ делится на $$$y = 1$$$.
  • $$$y = 7$$$ подходит, потому что $$$x \oplus y = 7 \oplus 7 = 0$$$ и $$$0$$$ делится как на $$$x = 7$$$, так и на $$$y = 7$$$.
  • $$$y = 9$$$ подходит, потому что $$$x \oplus y = 7 \oplus 9 = 14$$$ и $$$14$$$ делится на $$$x = 7$$$.