write a go solution for Description:
Given two positive integers n and m. Find the sum of all possible values of a_1bigoplusa_2bigoplusldotsbigoplusa_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_1bigoplusa_2bigoplusldotsbigoplusa_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 Format:
Each test consists of multiple test cases. The first line contains a single integer t (1<=t<=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<=n<=10^18,1<=m<=10^5) — the sum and the number of integers in the set, respectively.

Output Format:
For each test case, output the sum of all possible values of a_1bigoplusa_2bigoplusldotsbigoplusa_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.

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_1bigoplusa_2 are 5,5,1,1,5,5 respectively. So a_1bigoplusa_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_1bigoplusa_2bigoplusldotsbigoplusa_10=0. Therefore our answer is 0.. Output only the code with no comments, explanation, or additional text.