F. Нули и единицы
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Пусть $$$S$$$ — это строка Туэ-Морса. Другими словами, $$$S$$$ — это пронумерованная с $$$0$$$ бинарная строка бесконечной длины, построенная следующим образом:

  • Изначально $$$S$$$ равна «0».
  • Затем мы повторяем следующую операцию бесконечно много раз: конкатенируем $$$S$$$ с ее копией, в которой все биты заменены на противоположные по значению.

    Например, ниже показаны первые четыре операции:

    Номер операции$$$S$$$ до операции$$$S$$$ до операции с заменой битСконкатенированная $$$S$$$
    10101
    201100110
    30110100101101001
    401101001100101100110100110010110
    $$$\ldots$$$$$$\ldots$$$$$$\ldots$$$$$$\ldots$$$

Вам даны два положительных числа $$$n$$$ и $$$m$$$. Найдите количество позиций, в которых отличаются строки $$$S_0 S_1 \ldots S_{m-1}$$$ и $$$S_n S_{n + 1} \ldots S_{n + m - 1}$$$.

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

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

Единственная строка каждого набора содержит два положительных числа $$$n$$$ и $$$m$$$ ($$$1 \leq n,m \leq 10^{18}$$$).

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

Для каждого набора входных данных выведите одно целое число — количество позиций, в которых отличаются данные строки.

Пример
Входные данные
6
1 1
5 10
34 211
73 34
19124639 56348772
12073412269 96221437021
Выходные данные
1
6
95
20
28208137
48102976088
Примечание

Строка $$$S$$$ равна 0110100110010110....

В первом примере $$$S_0$$$ это «0», а $$$S_1$$$ это «1». Эти строки отличаются в $$$1$$$ позиции.

Во втором примере $$$S_0 S_1 \ldots S_9$$$ это «0110100110», а $$$S_5 S_6 \ldots S_{14}$$$ это «0011001011». Эти строки отличаются в $$$6$$$ позициях.