{"raw_statement":[{"iden":"statement","content":"给定两个正整数 $n,m$，求：\n\n$$\\sum_{i=1}^{n}\\sum_{j=1}^{m}\\left(i \\oplus j\\right) $$\n\n其中，$\\oplus$ 表示按位异或运算（即 C++ 中的 `^` 符号）。答案对 $998244353$ 取模。"},{"iden":"input","content":"本题包含多组数据。\n\n第一行输入一个整数 $T$，表示数据组数。\n\n接下来 $T$ 行，每行输入两个整数 $n,m$。"},{"iden":"output","content":"输出共 $T$ 行，每行一个整数，表示每组询问的答案。"},{"iden":"note","content":"#### 样例解释\n\n第一个样例第一组数据：\n\n$\\begin{aligned}&(1 \\oplus 1)+(1 \\oplus 2)+(2 \\oplus 1)+(2 \\oplus 2)\\\\=\\ &0+3+3+0\\\\=\\ &6\\end{aligned}$\n\n第二组数据：\n\n$\\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}$\n\n---\n\n#### 数据范围\n\n|子任务|$n,m \\leq$|特殊性质|分值|\n|:-:|:-:|:-:|:-:|\n|$1$|$10^3$|无|$10$|\n|$2$|$10^6$|无|$20$|\n|$3$|$10^{16}$|A|$20$|\n|$4$|$10^{16}$|无|$50$|\n\n- 特殊性质 A：保证 $n=2^p-1$，$m=2^q-1$，其中 $p,q\\in\\mathbb Z$。\n\n对于 $100\\%$ 的数据，保证 $1 \\leq n,m \\leq 10^{16}$，$1 \\leq T \\leq 50$。"}],"translated_statement":null,"sample_group":[["2\n2 2\n3 3","6\n12"],["2\n4 8\n8 9","144\n420"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}