题目描述

$Rubyonly$ 最近在研究数字，他发现：数字就是数，数就是数字。

$Rubyonly$ 对于每个数都有一个好感度，对于一个数 $x$ 的好感度是 $x$ 在二进制表示下 $1$ 的个数。例如，$Rubyonly$ 对 $3_{10} = 11_{2}$ 的好感度为 $2$，对 $11_{10} = 1011_{2}$ 的好感度为 $3$。

现在，他想知道在 $1\sim n$ 中，好感度为 $1\sim m$ 的数分别有多少个。

设好感度为 $i$ 的数的个数为 $num_i$，$Rubyonly$ 懒得去一个一个看这 $m$ 个数，他只想让你告诉他下式的结果在模 $\texttt{998244353}$ 意义下是多少。

这样的询问有很多次，$Rubyonly$ 希望你能依次回答。

输入格式

从文件 like.in 中读入数据。

第一行一个正整数 $T$，表示 $Rubyonly$ 的询问次数。

接下来 $T$ 行，每行两个正整数 $n$ 和 $m$，含义见题目描述。

输出格式

输出到文件 like.out 中。

输出 $T$ 行，每行一个整数，表示每次询问的答案。

2
7 3
10 4

12
17

数据范围

对于全部数据，满足：$1\leq T\leq 10^6$，$1\leq n \leq 10^{18}$，$1\leq m\leq 60$。