题目描述

在一张无限大的纸上有一个 $m \times m$ 的正方形印章。最初，印章的左下角与纸张的左下角对齐。你会得到两个长度为 $n$ 的整数序列 $x$ 和 $y$。对于每一步 $i$（从 $1$ 到 $n$），会发生以下操作：

• 将印章向右移动 $x_i$ 个单位，向上移动 $y_i$ 个单位。
• 将印章按压在纸上，在当前位置留下一个 $m \times m$ 的有色正方形。

注意，序列 $x$ 和 $y$ 的每个元素都满足特殊约束：$1 \le x_i, y_i \le m - 1$。

注意，你不会在纸张的左下角按压印章。具体可参考题目下方的说明图片。

可以证明，所有操作完成后，纸上的有色区域是一个连通的整体。请你求出这个有色区域的周长。

输入格式

每组测试数据包含多组测试用例。第一行包含一个整数 $t$（$1 \le t \le 1000$），表示测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 100$，$2 \le m \le 100$），分别表示操作次数和正方形印章的边长。

接下来的 $n$ 行，每行包含两个整数 $x_i$ 和 $y_i$（$1 \le x_i, y_i \le m - 1$），分别表示第 $i$ 次操作中印章向右和向上移动的距离。

注意，所有测试用例的 $n$ 之和没有额外限制。

输出格式

对于每个测试用例，输出一个整数，表示纸上有色区域的周长。

说明/提示

在第一个样例中，印章边长为 $3$，共按压 $4$ 次，坐标分别为 $(1, 1)$、$(3, 3)$、$(5, 4)$ 和 $(6, 6)$。纸张上的效果如下图所示：

其中，第一次按压形成的正方形为蓝色，第二次为红色，第三次为绿色，第四次为紫色。合并后的区域如下图所示：

从图中可以看出，这个区域的周长为 $32$。

由 ChatGPT 4.1 翻译

样例

3
4 3
1 1
2 2
2 1
1 2
1 2
1 1
6 7
3 6
1 1
3 1
6 6
5 4
6 1

32
8
96