CF1815D XOR Counting

记 $\bigoplus$ 表示按位异或运算。 给定整数 $n,m$。记一个序列 $a$ 是好的，当且仅当它是一个长度为 $m$ 的非负整数序列，且其元素之和恰好为 $n$。 求在好的序列 $a$ 中，$\bigoplus_{i=1}^ma_i$ 的所有可能取值之和对 $998244353$ 取模后的值。 对于一个 $\bm{\bigoplus_{i=1}^ma_i}$ 的可能取值，**无论有多少个**可以取得这个值的好的序列 $\bm{a}$，**这个值都应只被计入所求之和一次。** 每个测试点包含多组数据。

第一行输入一个整数 $t(1\leq t\leq10^4)$ 表示数据组数。 接下来每组数据含有一行两个整数 $n,m$ $(0\leq n\leq10^{18},1\leq m\leq10^5)$。

对于每组数据，输出一行一个整数表示 $\bigoplus_{i=1}^ma_i$ 的所有可能取值之和对 $998244353$ 取模后的值。

### 样例解释 对于样例一： - 所有好的序列 $a$ 为 $[69]$，其所有元素按位异或和为 $69$。 因此 $\bigoplus_{i=1}^ma_i$ 的所有可能取值为 $69$，故答案为 $69$。 对于样例二： - 所有好的序列 $a$ 为 $[5,0],[4,1],[3,2],[2,3],[4,1],[0,5]$，其所有元素按位异或和分别为 $5,5,1,1,5,5$。 因此 $\bigoplus_{i=1}^ma_i$ 的所有可能取值为 $1,5$，故答案为 $1+5$，即 $6$。 对于样例三： - 所有好的序列 $a$ 为 $[0,0,0,0,0,0,0,0,0,0]$，其所有元素按位异或和为 $0$。 因此 $\bigoplus_{i=1}^ma_i$ 的所有可能取值为 $0$，故答案为 $0$。