D. XOR Countingtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputGiven 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.InputEach 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.OutputFor 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
769 15 20 10420 6912 2673 341000000000000000000 10Output
69
6
0
44310
42
1369
216734648
NoteFor 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.
769 15 20 10420 6912 2673 341000000000000000000 10
69 6 0 44310 42 1369 216734648 
['bitmasks', 'combinatorics', 'dp', 'math', '*2600']