题目描述

不要回答！不要回答！不要回答！——1937 号观察员

危机纪元 10 年。

面对三体危机，人类为了保证存活下来，只好拼命发展科技以避免在末日战役中灭亡。

所以现在高维数学进入了小学教材……

于是你现在需要解一道未来小学三年级数学题：

众所周知，正方形有 $4$ 个点， $4$ 条边；正方体有 $8$ 个点， $12$ 条边，$6$ 个面，定义点为零维基础图形，线段为一维基础图形，正方形为二维基础图形，正方体为三维基础图形...，那么请问，一个 $n$ 维基础图形包含多少个 $m$ 维基础图形呢 $(m \leq n)$？

多次询问，输出对 $998244353$ 取模。

输入格式

第一行一个正整数 $T$ 表示数据组数。

下接 $T$ 行，每行两个自然数 $n, m$，描述一组数据。

输出格式

输出 $T$ 行，每行一个数字表示答案。

样例

input

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

output

8
12
6
1
223544257
155250
424453971

数据范围与提示

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

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