在一张无限大的纸上有一个 $$$m$$$ by $$$m$$$ 的方形邮票。最初,方形图章的左下角与纸张的左下角对齐。给定两个整数序列 $$$x$$$ 和 $$$y$$$,每个长度为 $$$n$$$。对于从 $$$1$$$ 到 $$$n$$$ 的每个步骤 $$$i$$$,会发生以下情况:
- 将标记向右移动 $$$x_i$$$ 个单位,向上移动 $$$y_i$$$ 个单位。
- 将印章压到纸上,在其当前位置留下 $$$m$$$ 乘 $$$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$$$ 行的第 $$$i$$$ 行包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$1 \le x_i, y_i \le m - 1$$$) - 分别是在第 $$$i$$$ 操作期间图章将向右和向上移动的距离。
请注意,所有测试用例的 $$$n$$$ 总和没有限制。
输出
对于每个测试用例,输出一个整数,表示纸上彩色形状的周长。
示例
输入 #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
输出 #1
32 8 96
注意
在第一个示例中,图章的边长为 $$$3$$$,并在坐标 $$$(1, 1)$$$、$$$(3, 3)$$$、$$$(5, 4)$$$ 和 $$$(6, 6)$$$ 处按下 $$$4$$$ 次。之后这张纸看起来像这样:
此处,第一次按形成的正方形颜色为蓝色,第二次为红色,第三次为绿色,第四次为紫色。我们需要计算其周长的组合形状如下所示:
从图中可以看出,这个形状的周长为$$$32$$$。