A67278.汉明距离Ⅱ

本题与汉明距离Ⅰ题面完全一样，只有数据范围不同。

具体而言，汉明距离是一种常见的度量两个非负整数之间相似程度的方法。两个非负整数 $x$ 和 $y$ 的汉明距离定义为 $x$ 和 $y$ 的二进制表示中，不同的位数。汉明距离可形式化定义如下：

$$d_H(x,y)=\sum_{i=0}^{\infty} I\left( \left(x\&2^i\right)\neq\left(y\&2^i\right) \right)$$

其中 $x\&y$ 表示 $x$ 和 $y$ 的按位与运算，$I$ 表示指示函数，即当括号内的条件成立时，$I$ 的值为 $1$，否则为 $0$。

现在，你需要判断区间 $[0, n]$ 内有多少个不同的数对 $(x, y)$ ($0\le x<y\le n$)，满足 $x$ 和 $y$ 的汉明距离小于等于 $k$，即 $d_H(x,y)\le k$。答案可能很大，你只需要输出答案对 $998244353$ 取模的结果。

每个测试输入包含多个测试用例。输入的第一行包含一个正整数 $t$，表示测试用例的组数。测试用例的描述如下：

每个测试用例的唯一一行包含两个正整数 $n$ 和 $k$，其含义见题目描述

对于每个测试用例，输出的唯一一行包含一个整数，表示答案对 $998244353$ 取模的结果。

数据范围

• $1 \le t \le 10^6$。
• $1\le n\le 10^6, 1 \le 2^{k-1} \le n$。