310330: CF1816F. XOR Counting

F. XOR Countingtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

Input

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.

Output

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

ExampleInput

7
69 1
5 2
0 10
420 69
12 26
73 34
1000000000000000000 10

Output

69
6
0
44310
42
1369
216734648

Note

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

题目大意：
给定两个正整数 n 和 m。求所有可能的 a_1⊕a_2⊕…⊕a_m 的和，其中 a_1,a_2,…,a_m 是非负整数，且 a_1+a_2+…+a_m=n。注意，所有可能的 a_1⊕a_2⊕…⊕a_m 的值都应该恰好被计算一次。由于答案可能非常大，请将答案模上 998244353 输出。这里的 ⊕ 表示按位异或操作。

输入数据格式：
每个测试包含多个测试用例。第一行包含一个整数 t（1≤t≤10^4）——测试用例的数量。接下来是每个测试用例的描述。
每个测试用例的第一行包含两个整数 n 和 m（0≤n≤10^18, 1≤m≤10^5）——集合中的数字之和和数字的数量。

输出数据格式：
对于每个测试用例，输出在所有非负整数 a_1,a_2,…,a_m 中，满足 a_1+a_2+…+a_m=n 的所有可能的 a_1⊕a_2⊕…⊕a_m 的和。由于答案可能非常大，请将答案模上 998244353 输出。题目大意： 给定两个正整数 n 和 m。求所有可能的 a_1⊕a_2⊕…⊕a_m 的和，其中 a_1,a_2,…,a_m 是非负整数，且 a_1+a_2+…+a_m=n。注意，所有可能的 a_1⊕a_2⊕…⊕a_m 的值都应该恰好被计算一次。由于答案可能非常大，请将答案模上 998244353 输出。这里的 ⊕ 表示按位异或操作。 输入数据格式： 每个测试包含多个测试用例。第一行包含一个整数 t（1≤t≤10^4）——测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含两个整数 n 和 m（0≤n≤10^18, 1≤m≤10^5）——集合中的数字之和和数字的数量。 输出数据格式： 对于每个测试用例，输出在所有非负整数 a_1,a_2,…,a_m 中，满足 a_1+a_2+…+a_m=n 的所有可能的 a_1⊕a_2⊕…⊕a_m 的和。由于答案可能非常大，请将答案模上 998244353 输出。