Problem Description

Given two positive integers $n, m$, compute:

$$\sum_{i=1}^{n}\sum_{j=1}^{m}\left(i \oplus j\right)$$

Here, $\oplus$ denotes the bitwise XOR operation (i.e., the ^ operator in C++). Output the answer modulo $998244353$.

Input Format

This problem contains multiple test cases.

The first line contains an integer $T$, the number of test cases.

The next $T$ lines each contain two integers $n, m$.

Output Format

Output $T$ lines, each containing one integer, the answer for the corresponding test case.

2
2 2
3 3

6
12

2
4 8
8 9

144
420

Hint

Sample Explanation

For the first sample test case:

$\begin{aligned}&(1 \oplus 1)+(1 \oplus 2)+(2 \oplus 1)+(2 \oplus 2)\\=\ &0+3+3+0\\=\ &6\end{aligned}$

For the second sample test case:

$\begin{aligned}&(1 \oplus 1)+(1 \oplus 2)+(1 \oplus 3)+(2 \oplus 1)+(2 \oplus 2)+(2 \oplus 3)+(3 \oplus 1)+(3 \oplus 2)+(3 \oplus 3)\\=\ &0+3+2+3+0+1+2+1+0\\=\ &12\end{aligned}$

---

Constraints

Subtask	$n, m \leq$	Special Property	Points
$1$	$10^3$	None	$10$
$2$	$10^6$		$20$
$3$	$10^{16}$	A
$4$		None	$50$

• Special Property A: It is guaranteed that $n = 2^p - 1$ and $m = 2^q - 1$, where $p, q \in \mathbb Z$.

For $100\%$ of the testdata, it is guaranteed that $1 \leq n, m \leq 10^{16}$ and $1 \leq T \leq 50$.

Translated by ChatGPT 5