CF1734F.Zeros and Ones

Let $S$ be the Thue-Morse sequence. In other words, $S$ is the $0$-indexed binary string with infinite length that can be constructed as follows:

• Initially, let $S$ be "0".

• Then, we perform the following operation infinitely many times: concatenate $S$ with a copy of itself with flipped bits.

  For example, here are the first four iterations:

  Iteration

  $S$ before iteration

  $S$ before iteration with flipped bits

  Concatenated $S$

  1

  0

  1

  01

  2

  01

  10

  0110

  3

  0110

  1001

  01101001

  4

  01101001

  10010110

  0110100110010110

  $\ldots$

  $\ldots$

  $\ldots$

  $\ldots$

You are given two positive integers $n$ and $m$. Find the number of positions where the strings $S_0 S_1 \ldots S_{m-1}$ and $S_n S_{n + 1} \ldots S_{n + m - 1}$ are different.

设 $S$ 为Thue-Morse 序列。换言之，$S$ 是一个从索引 $0$ 开始的无限长二进制字符串，其构造方式如下：

• 初始时，令 $S$ 为 "0"。

• 然后，无限次执行以下操作：将 $S$ 与其各位取反（即 0 变 1，1 变 0）后的副本拼接。

  例如，前四次迭代过程如下：

  迭代次数

  迭代前的 $S$

  迭代前的 $S$（各位取反）

  拼接后的新 $S$

  1

  0

  1

  01

  2

  01

  10

  0110

  3

  0110

  1001

  01101001

  4

  01101001

  10010110

  0110100110010110

  $\ldots$

  $\ldots$

  $\ldots$

  $\ldots$

给定两个正整数 $n$ 和 $m$。求字符串 $S_0 S_1 \ldots S_{m-1}$ 与 $S_n S_{n + 1} \ldots S_{n + m - 1}$ 在多少个位置上字符不同。

Each test contains multiple test cases. The first line of the input contains a single integer $t$ ($1 \le t \le 100$) — the number of test cases. The description of the test cases follows.

The first and only line of each test case contains two positive integers, $n$ and $m$ respectively ($1 \leq n,m \leq 10^{18}$).

每个测试包含多个测试用例。输入的第一行包含一个整数 $t$（$1 \le t \le 100$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例仅有一行，包含两个正整数 $n$ 和 $m$（$1 \leq n,m \leq 10^{18}$）。

For each testcase, output a non-negative integer — the Hamming distance between the two required strings.

对于每个测试用例，输出一个非负整数——即两个指定字符串之间的汉明距离。

The string $S$ is equal to 0110100110010110....

In the first test case, $S_0$ is "0", and $S_1$ is "1". The Hamming distance between the two strings is $1$.

In the second test case, $S_0 S_1 \ldots S_9$ is "0110100110", and $S_5 S_6 \ldots S_{14}$ is "0011001011". The Hamming distance between the two strings is $6$.

字符串 $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$。