A15962 | 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](https://en.wikipedia.org/wiki/Bitwise_operation#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.

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