AT_abc406_e.[ABC406E] Popcount Sum 3

给定正整数 $N, K$。
请求出所有小于等于 $N$ 的正整数 $x$ 中，满足以下条件的数的总和，并将结果对 $998244353$ 取模。

• $x$ 的 $\mathrm{popcount}$ 值恰好为 $K$。

给定 $T$ 个测试用例，请分别求出答案。

$\mathrm{popcount}$ 指的是，对于正整数 $y$，其 $\mathrm{popcount}$ 值 $\mathrm{popcount}(y)$ 表示 $y$ 在二进制表示中数字 $1$ 出现的次数。例如，$\mathrm{popcount}(5)=2$，$\mathrm{popcount}(16)=1$，$\mathrm{popcount}(25)=3$。

输入按以下格式从标准输入给出。

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

$\mathrm{case}_i$ 表示第 $i$ 个测试用例。每个测试用例按以下格式给出。

$N$ $K$

输出 $T$ 行。第 $i$ 行 $(1 \leq i \leq T)$ 输出第 $i$ 个测试用例的答案。

「数据范围」

• $1 \leq T \leq 100$
• $1 \leq N < 2^{60}$
• $1 \leq K \leq 60$
• $T, N, K$ 均为整数

「样例 1 解释」

对于第 $1$ 个测试用例，小于等于 $20$ 的正整数中，$\mathrm{popcount}$ 值为 $2$ 的数有 $3, 5, 6, 9, 10, 12, 17, 18, 20$，共 $9$ 个，它们的总和是 $100$。

$100$ 对 $998244353$ 取模的结果是 $100$，因此第 $1$ 行输出 $100$。

请注意需要输出对 $998244353$ 取模的余数。