考虑一个 $N \times N$ 的方形地图。我们用 $(i, j)$ 表示单元格的坐标，其中 $1 \le i, j \le N$。每个单元格的颜色要么是白色，要么是黑色。所有单元格的初始颜色均为白色。该地图支持操作 $flip([x_{low}, x_{high}], [y_{low}, y_{high}])$，该操作会翻转矩形区域 $[x_{low}, x_{high}] \times [y_{low}, y_{high}]$ 内每个单元格的颜色。给定一系列翻转操作，我们的问题是计算最终地图中黑色单元格的数量。我们在下例中进行说明。图 (a) 显示了初始地图。接着，我们调用 $flip([2, 4], [1, 3])$ 得到图 (b)。然后，我们调用 $flip([1, 5], [3, 5])$ 得到图 (c)。该地图包含 18 个黑色单元格。

(a) 初始地图 (b) 翻转矩形 [2,4]×[1,3] 后 (c) 翻转矩形 [1,5]×[3,5] 后

输入格式

第一行包含测试用例的数量 $T$ ($T < 10$)。每个测试用例以一行开始，包含两个整数 $N$ 和 $K$ ($1 < N, K < 10000$)，其中 $N$ 是地图大小参数，$K$ 是翻转操作的数量。接下来的每一行对应一个翻转操作，包含四个整数：$x_{low}, x_{high}, y_{low}, y_{high}$。

输出格式

对于每个测试用例，输出一行答案。

样例

输入 1

1
5 2
2 4 1 3
1 5 3 5

输出 1

18