一家飞机制造公司想要优化其产品以服务客运航空公司。公司最新的研究表明，大部分延误都是由登机缓慢造成的。

大多数中型飞机采用 3-3 座位布局，这意味着每一排有 6 个座位：左侧 3 个座位，中间一个过道，右侧 3 个座位。在左侧和右侧，分别有一个靠窗座位、一个中间座位和一个靠过道座位。即使在飞机上没有其他人的情况下，被分配到靠过道座位的乘客登机所需的时间也明显少于被分配到靠窗座位的乘客。

公司决定将布局的“不便程度”定义为单排中每个座位到最近过道的距离之和。座位到过道的距离是指它们之间的座位数。对于 3-3 布局，靠窗座位的距离为 2，中间座位的距离为 1，靠过道座位的距离为 0。3-3 布局的不便程度为 $(2 + 1 + 0) + (0 + 1 + 2) = 6$。3-5-3 布局的不便程度为 $(2 + 1 + 0) + (0 + 1 + 2 + 1 + 0) + (0 + 1 + 2) = 10$。

形式上，一个布局是一个正整数序列 $a_1, a_2, \dots, a_{k+1}$，其中第 $i$ 组有 $a_i$ 个座位，共有 $k$ 个过道，第 $i$ 个过道位于第 $i$ 组和第 $i+1$ 组之间。这意味着在布局中，每个过道必须始终位于两个座位之间，因此过道不能靠近窗户，且两个过道之间不能相邻。

公司决定设计一种包含 $n$ 个座位和 $k$ 个过道的布局，并使其不便程度最小。请帮助他们找出所有 $n$ 个座位和 $k$ 个过道的布局中的最小不便程度，并计算出满足该最小不便程度的布局数量，结果对 $998\,244\,353$ 取模。

输入格式

第一行包含一个整数 $t$ —— 需要解决的测试用例数量 ($1 \le t \le 10^5$)。

对于每个测试用例，只有一行，包含 $n$ 和 $k$ —— 一排中的座位数和过道数 ($2 \le n \le 10^9$; $1 \le k \le 10^5$; $k < n$)。

所有测试用例中 $k$ 的总和不超过 $10^6$。

输出格式

对于每个测试用例，输出两个整数 —— 所有可能布局中的最小不便程度，以及不便程度达到最小的布局数量（对 $998\,244\,353$ 取模）。

样例

输入 1

8
4 1
3 2
4 2
5 2
6 1
6 2
1000000000 1
9 2

输出 1

2 1
0 1
0 1
1 3
6 1
2 4
249999999500000000 1
6 3

说明

在最后一个测试用例 $9\ 2$ 中，不便程度为 $6$ 的可能布局有 3-4-2、2-4-3 和 2-5-2。