给定两个整数 $n, k$ ($2 \le k < n$)。

对于一个仅由 0 和 1 组成的数组 $a_1, a_2, \dots, a_n$，我们定义长度为 $n$ 的数组 $f(a)$ 如下：

• $f(a)_i = a_i + a_{i+1} + \dots + a_{i+k-2} + a_{i+k-1}$（此处假设 $a_{n+i} = a_i$，即数字排列在一个圆环上）。

例如，当 $n = 4, k = 2$ 时，$f([0, 1, 1, 0]) = [1, 2, 1, 0]$。

考虑所有 $2^n$ 种可能的数组 $a$，并对其中每一个数组求出 $f(a)$。在这些结果中，有多少个不同的数组？由于答案可能非常大，请输出该数量对 998244353 取模的结果。如果两个数组在至少一个位置上不同，则认为它们是不同的。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 10^5$)，表示测试用例的数量。接下来是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n, k$ ($2 \le k < n \le 10^6$)。

输出格式

对于每个测试用例，输出不同数组 $f(a)$ 的数量，对 998244353 取模。

样例

输入 1

4
3 2
4 2
42 3
123123 123

输出 1

8
15
780086989
126500246

说明

对于 $n = 3, k = 2$，共有 8 个不同的由 0 和 1 组成的数组 $a$。对于这些数组，其对应的 $f(a)$ 两两不同。

对于 $n = 4, k = 2$，共有 16 个不同的由 0 和 1 组成的数组 $a$。唯一一对满足 $f(a)$ 相同的数组是 $[0, 1, 0, 1]$ 和 $[1, 0, 1, 0]$：对于这两个数组，$f(a)$ 均为 $[1, 1, 1, 1]$。