8999: [yosupo] Number Theory - Nim Product
[Creator : ]
Description
There are $T$ test cases.
For each test case, you are given two nonnegative integers $A$ and $B$.
Calculate the nim product $A \otimes B$.
The nim sum and the nim product for nonnegative integers are defined recursively as follows:
For each test case, you are given two nonnegative integers $A$ and $B$.
Calculate the nim product $A \otimes B$.
The nim sum and the nim product for nonnegative integers are defined recursively as follows:
- $a \oplus b = \operatorname{mex}(\\{ a' \oplus b \mid a' < a \\} \cup \\{ a \oplus b' \mid b' < b \\})$
- $a \otimes b = \operatorname{mex}\\{ (a' \otimes b) \oplus (a \otimes b') \oplus (a' \otimes b') \mid a' < a,\, b' < b \\}$
Input
$T$
$A_0$ $B_0$
$\vdots$
$A_{T-1}$ $B_{T-1}$
$A_0$ $B_0$
$\vdots$
$A_{T-1}$ $B_{T-1}$
Output
$\mathit{answer}_0$
$\vdots$
$\mathit{answer}_{T-1}$
$\vdots$
$\mathit{answer}_{T-1}$
Constraints
$0 \le T \le 10^6$
$0 \le A < 2^{64}$
$0 \le B < 2^{64}$
$0 \le A < 2^{64}$
$0 \le B < 2^{64}$
Sample 1 Input
11
5 0
5 1
5 2
5 3
5 4
5 5
5 6
5 7
5 8
3141 5926
18446744073709551615 18446744073709551615
Sample 1 Output
0
5
10
15
2
7
8
13
3
14994
11290409524105353207