无额外样例。

题目描述

众所周知，正方形有 4 个点，4 条边；正方体有 8 个点，12 条边，6 个面。定义“点”为零维基础图形，“线段”为一维基础图形，“正方形”为二维基础图形，“正方体”为三维基础图形……

问题是：一个 n 维基础图形包含多少个 m 维基础图形呢？(m ≤ n) 输出答案 mod 998244353。

多组数据。

输入格式

第一行：一个整数 T, 表示数据组数。

接下来 T 行，每行两个整数 n, m, 描述一组数据。

输出格式

共 T 行，每组数据的答案占一行。

样例输入

7
3 0
3 1
3 2
3 3
48545 1
77625 77624
93574 83513

样例输出

8
12
6
1
223544257
155250
424453971

数据范围

对于全部数据，$T ≤ 10^5, 0 ≤ m ≤ n ≤ 10^5$。

存在 $10 \%$ 的数据满足 $m = 1$

存在 $10 \%$ 的数据满足 $m = n - 1$

存在 $10 \%$ 的数据满足 $m = 2$

存在 $10 \%$ 的数据满足 $m = n - 2$