Zeros and Ones

题意翻译

$S$ 是一个 [Thue-Morse序列](https://baike.baidu.com/item/Thue-Morse%E5%BA%8F%E5%88%97/13028975)。它是一个由以下方式生成的无限长 01 字符串： - 最初，令 $ S $ 为 "0"。 - 随后进行以下操作无穷多次：将 $ S $ 与各位取反后的 $ S $ 连接。以前 4 次操作为例： | 次数 | $ S $ | 取反后的 $ S $ | 操作后得到的 $ S $ | | :----------- | :----------- | :----------- | :----------- | | 1 | 0 | 1 | 01 | | 2 | 01 | 10 | 0110 | | 3 | 0110 | 1001 | 01101001 | | 4 | 01101001 | 10010110 | 0110100110010110 | 给定 2 个正整数 $n$ 和 $m$，求 $S_0S_1 \cdots S_{m-1} $ 和 $S_{n}S_{n+1} \cdots S_{n+m-1}$ 有几位不同。 输入包含多组数据。第一行读入一个正整数 $t$ 表示数据组数，此后每组数据仅包含一行，每行读入两个正整数 $n,m$。 对于每组数据，输出为一行一个非负整数。

题目描述

Let $ S $ be the [Thue-Morse sequence](https://en.wikipedia.org/wiki/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 bitsConcatenated $ S $ 1010120110011030110100101101001401101001100101100110100110010110 $ \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.

输入输出格式

输入格式

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} $ ).

输出格式

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

输入输出样例

输入样例 #1

6
1 1
5 10
34 211
73 34
19124639 56348772
12073412269 96221437021

输出样例 #1

1
6
95
20
28208137
48102976088

说明

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$ 是一个 [Thue-Morse序列](https://baike.baidu.com/item/Thue-Morse%E5%BA%8F%E5%88%97/13028975)。它是一个由以下方式生成的无限长 01 字符串： - 最初，令 $ S $ 为 "0"。 - 随后进行以下操作无穷多次：将 $ S $ 与各位取反后的 $ S $ 连接。以前 4 次操作为例： | 次数 | $ S $ | 取反后的 $ S $ | 操作后得到的 $ S $ | | :----------- | :----------- | :----------- | :----------- | | 1 | 0 | 1 | 01 | | 2 | 01 | 10 | 0110 | | 3 | 0110 | 1001 | 01101001 | | 4 | 01101001 | 10010110 | 0110100110010110 | 给定 2 个正整数 $n$ 和 $m$，求 $S_0S_1 \cdots S_{m-1} $ 和 $S_{n}S_{n+1} \cdots S_{n+m-1}$ 有几位不同。 输入包含多组数据。第一行读入一个正整数 $t$ 表示数据组数，此后每组数据仅包含一行，每行读入两个正整数 $n,m$。 对于每组数据，输出为一行一个非负整数。