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

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

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

$$$^{\text{∗}}$$$Число $$$b$$$ является делителем числа $$$a$$$, если существует целое число $$$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
6 9
5 7
2 3
6 4
4 1
Выходные данные
3
2
1
1
0
Примечание

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

  • $$$y = 4$$$ подходит, потому что $$$x \oplus y = 6 \oplus 4 = 2$$$ и $$$2$$$ является делителем как $$$x = 6$$$, так и $$$y = 4$$$.
  • $$$y = 5$$$ подходит, потому что $$$x \oplus y = 6 \oplus 5 = 3$$$ и $$$3$$$ является делителем $$$x = 6$$$.
  • $$$y = 7$$$ подходит, потому что $$$x \oplus y = 6 \oplus 7 = 1$$$ и $$$1$$$ является делителем как $$$x = 6$$$, так и $$$y = 7$$$.

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

  • $$$y = 4$$$ подходит, потому что $$$x \oplus y = 5 \oplus 4 = 1$$$ и $$$1$$$ является делителем как $$$x = 5$$$, так и $$$y = 4$$$.
  • $$$y = 6$$$ подходит, потому что $$$x \oplus y = 5 \oplus 6 = 3$$$ и $$$3$$$ является делителем $$$y = 6$$$.