310941: CF1912B. Blueprint for Seating

B. Blueprint for Seatingtime limit per test3 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard output

An aircraft manufacturing company wants to optimize their products for passenger airlines. The company's latest research shows that most of the delays happen because of slow boarding.

Most of the medium-sized aircraft are designed with 3-3 seat layout, meaning each row has 6 seats: 3 seats on the left side, a single aisle, and 3 seats on the right side. At each of the left and right sides there is a window seat, a middle seat, and an aisle seat. A passenger that boards an aircraft assigned to an aisle seat takes significantly less time than a passenger assigned to a window seat even when there is no one else in the aircraft.

The company decided to compute an inconvenience of a layout as the total sum of distances from each of the seats of a single row to the closest aisle. The distance from a seat to an aisle is the number of seats between them. For a 3-3 layout, a window seat has a distance of 2, a middle seat — 1, and an aisle seat — 0. The inconvenience of a 3-3 layout is $(2+1+0)+(0+1+2)=6$. The inconvenience of a 3-5-3 layout is $(2+1+0)+(0+1+2+1+0)+(0+1+2)=10$.

Formally, a layout is a sequence of positive integers $a_1, a_2, \ldots, a_{k+1}$ — group $i$ having $a_i$ seats, with $k$ aisles between groups, the $i$-th aisle being between groups $i$ and $i+1$. This means that in a layout each aisle must always be between two seats, so no aisle can be next to a window, and no two aisles can be next to each other.

The company decided to design a layout with a row of $n$ seats, $k$ aisles and having the minimum inconvenience possible. Help them find the minimum inconvenience among all layouts of $n$ seats and $k$ aisles, and count the number of such layouts modulo $998\,244\,353$.

Input

The first line contains an integer $t$ — the number of test cases you need to solve ($1 \le t \le 10^5$).

For each of the test cases, there is a single line containing $n$ and $k$ — the number of seats, and the number of aisles in a row ($2 \le n \le 10^9$; $1 \le k \le 10^5$; $k < n$).

The total sum of $k$ in all $t$ given test cases does not exceed $10^6$.

Output

For each test case print two integers — the minimum inconvenience among all possible layouts, and the number of layouts with the minimum inconvenience modulo $998\,244\,353$.

ExampleInput

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

Output

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

Note

In the last test case of 9 2 the possible layouts with the minimum inconvenience of 6 are 3-4-2, 2-4-3, and 2-5-2.

题目大意：
一个飞机制造公司希望优化他们的客机产品，他们的最新研究表明，大部分延误是因为乘客登机速度慢。大多数中型飞机采用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, \ldots, 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 $)。
- 所有 $ t $ 个给定测试用例的 $ k $ 之和不超过 $ 10^6 $。

输出：
- 对于每个测试用例，打印两个整数——所有可能布局中的最小不便程度，以及具有最小不便程度的布局数量模 $ 998\,244\,353 $。题目大意： 一个飞机制造公司希望优化他们的客机产品，他们的最新研究表明，大部分延误是因为乘客登机速度慢。大多数中型飞机采用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, \ldots, 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 $)。 - 所有 $ t $ 个给定测试用例的 $ k $ 之和不超过 $ 10^6 $。 输出： - 对于每个测试用例，打印两个整数——所有可能布局中的最小不便程度，以及具有最小不便程度的布局数量模 $ 998\,244\,353 $。