#6501. 「雅礼集训 2018 Day4」Cube

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

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

危机纪元 10 年。

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

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

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

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

多次询问,输出对 998244353 取模。

输入格式

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

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

输出格式

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

样例

样例输入 1

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

样例输出 1

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