Nim 积（Nim Product over $\mathbb{F}_{2^{64}}$）

问题描述

给定 $T$ 组测试数据。对每组，输入两个非负整数 $A$ 和 $B$，计算它们的 Nim 积 $A \otimes B$，其中运算在域 $\mathbb{F}_{2^{64}}$ 上定义。

Nim 和（$\oplus$）与 Nim 积（$\otimes$）递归定义如下：

• $a \oplus b = \operatorname{mex}\big( \{a' \oplus b \mid a' < a\} \cup \{a \oplus b' \mid b' < b\} \big)$
• $a \otimes b = \operatorname{mex}\big( \{ (a' \otimes b) \oplus (a \otimes b') \oplus (a' \otimes b') \mid a' < a,\ b' < b \} \big)$

注：此处“$\mathbb{F}_{2^{64}}$”为题目标注，但实际 Nim 积是定义在非负整数上的二元运算，满足 $a \otimes b < 2^{64}$ 当 $a, b < 2^{64}$；本题约束保证 $A, B < 2^{64}$，故结果仍在 64 位无符号整数范围内。

约束条件

• $1 \leq T \leq 10^6$
• $0 \leq A, B < 2^{64}$

输入格式

$T$
$A_0\ B_0$
$A_1\ B_1$
:
$A_{T-1}\ B_{T-1}$

输出格式

$answer_0$
$answer_1$
:
$answer_{T-1}$

11
5 0
5 1
5 2
5 3
5 4
5 5
5 6
5 7
5 8
3141 5926
18446744073709551615 18446744073709551615

0
5
10
15
2
7
8
13
3
14994
11290409524105353207