P9223 "PEOI Rd1" XOR (xor).

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$.

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 $T$ lines, each containing one integer, the answer for the corresponding test case.

#### 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$|None|$20$| |$3$|$10^{16}$|A|$20$| |$4$|$10^{16}$|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