CF1815D.XOR Counting

Given two positive integers $n$ and $m$. Find the sum of all possible values of $a_1\bigoplus a_2\bigoplus\ldots\bigoplus a_m$, where $a_1,a_2,\ldots,a_m$ are non-negative integers such that $a_1+a_2+\ldots+a_m=n$.

Note that all possible values $a_1\bigoplus a_2\bigoplus\ldots\bigoplus a_m$ should be counted in the sum exactly once.

As the answer may be too large, output your answer modulo $998244353$.

Here, $\bigoplus$ denotes the bitwise XOR operation.

给定两个正整数 $n$ 和 $m$。求所有可能的 $a_1\bigoplus a_2\bigoplus\ldots\bigoplus a_m$ 的值之和，其中 $a_1,a_2,\ldots,a_m$ 为非负整数，且满足 $a_1+a_2+\ldots+a_m=n$。

注意：所有可能的值 $a_1\bigoplus a_2\bigoplus\ldots\bigoplus a_m$ 在求和中仅计算一次（即去重后求和）。

由于答案可能过大，请将结果对 $998244353$ 取模后输出。

此处，$\bigoplus$ 表示按位异或运算（bitwise XOR）。

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of test cases follows.

The first and only line of each test case contains two integers $n$ and $m$ ($0\le n\le 10^{18}, 1\le m\le 10^5$) — the sum and the number of integers in the set, respectively.

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例仅有一行，包含两个整数 $n$ 和 $m$（$0\le n\le 10^{18}, 1\le m\le 10^5$），分别表示集合中所有整数的和以及集合中整数的个数。

For each test case, output the sum of all possible values of $a_1\bigoplus a_2\bigoplus\ldots\bigoplus a_m$ among all non-negative integers $a_1,a_2,\ldots,a_m$ with $a_1+a_2+\ldots+a_m=n$. As the answer may be too large, output your answer modulo $998244353$.

对于每组测试数据，输出所有满足 $a_1+a_2+\ldots+a_m=n$ 的非负整数序列 $a_1,a_2,\ldots,a_m$ 对应的 $a_1\bigoplus a_2\bigoplus\ldots\bigoplus a_m$ 的所有可能取值之和。由于答案可能过大，请将结果对 $998244353$ 取模后输出。

For the first test case, we must have $a_1=69$, so it's the only possible value of $a_1$, therefore our answer is $69$.

For the second test case, $(a_1,a_2)$ can be $(0,5), (1,4), (2,3), (3,2), (4,1)$ or $(5,0)$, in which $a_1\bigoplus a_2$ are $5,5,1,1,5,5$ respectively. So $a_1\bigoplus a_2$ can be $1$ or $5$, therefore our answer is $1+5=6$.

For the third test case, $a_1,a_2,\ldots,a_{10}$ must be all $0$, so $a_1\bigoplus a_2\bigoplus\ldots\bigoplus a_{10}=0$. Therefore our answer is $0$.

对于第一个测试用例，必须有 $a_1=69$，因此 $a_1$ 的唯一可能取值为 $69$，故答案为 $69$。

对于第二个测试用例，$(a_1,a_2)$ 可以是 $(0,5), (1,4), (2,3), (3,2), (4,1)$ 或 $(5,0)$，对应地，$a_1\bigoplus a_2$ 的值分别为 $5,5,1,1,5,5$。因此 $a_1\bigoplus a_2$ 的可能取值为 $1$ 或 $5$，故答案为 $1+5=6$。

对于第三个测试用例，$a_1,a_2,\ldots,a_{10}$ 必须全为 $0$，因此 $a_1\bigoplus a_2\bigoplus\ldots\bigoplus a_{10}=0$。故答案为 $0$。