Пусть \(S\) — это строка Туэ-Морса. Другими словами, \(S\) — это пронумерованная с \(0\) бинарная строка бесконечной длины, построенная следующим образом:
Например, ниже показаны первые четыре операции:
Вам даны два положительных числа \(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}\)).
Для каждого набора входных данных выведите одно целое число — количество позиций, в которых отличаются данные строки.
Строка \(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\) позициях.
6 1 1 5 10 34 211 73 34 19124639 56348772 12073412269 96221437021
1 6 95 20 28208137 48102976088
3000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач