← 返回题目列表

Codeforces · 1734/F

F. 零和一

中文机器翻译题面 查看原题

令 $$$S$$$ 为 Thue-Morse 序列。换句话说,$$$S$$$ 是 $$$0$$$ 索引的无限长度的二进制字符串,可以按如下方式构造:

- 最初,让 $$$S$$$ 为“0”。
- 然后,我们无限次执行以下操作:将 $$$S$$$ 与其自身的副本(带翻转位)连接起来。例如,这里是前四次迭代: 迭代$$$S$$$ 迭代前$$$S$$$ 迭代前翻转位连接$$$S$$$1010120110011030110100101101001401101001100101100110100110010110$$$\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}$$$)。

输出

对于每个测试用例,输出一个非负整数 - 两个所需字符串之间的汉明距离。

示例

输入 #1

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

输出 #1

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$$$。