# Nim Product ($\mathbb{F}_{2^{64}}$)

AC一覧

## Problem Statement問題文

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:

• $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 \}$

## Constraints制約

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

## Input入力

$T$
$A_0$ $B_0$
$\vdots$
$A_{T-1}$ $B_{T-1}$


## Output出力

$\mathit{answer}_0$
$\vdots$
$\mathit{answer}_{T-1}$


### # 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


Timelimit: 10 secs

Before submitting, please confirm terms and conditions