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