时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

小王最近在开发一种新的游戏引擎,但是最近遇到了性能瓶颈。于是他打算从最基本的画线功能开始分析优化。画线其实就是调用一次drawline命令,根据给出的两端坐标,在屏幕画出对应的线段。但是小王发现,很多的drawline其实可以合并在一起,譬如下图中的线段(2,3)-(4,5)和线段(3,4)-(6,7),其实可以合并为一次drawline命令,直接画出线段(2,3)-(6,7)。当然有些线段是无法合并的,如线段(-3,8)-(1,8)和线段(3,8)-(6,8),就必须调用两次drawline命令。

画线示意图。注意颜色只是用于区分,实际线段都是黑色

 

给出N条drawline指令以及对应的线段坐标,小王想知道,实际最少用多少次drawline指令就可以画出来。

小王想先从最简单的情况开始分析优化,所以线段只包含四种情况:水平线段,垂直线段以及正反45度的线段。

输入

每个输入数据包含多个测试点。

第一行为测试点的个数 S ≤ 10。之后是 个测试点的数据。

每个测试点的第一行为 N(≤ 105)。之后是 行,每行包含4个整数:x0y0x1y1,表示线段(x0,y0)-(x1,y1),坐标的范围在[-108, 108],保证线段的长度大于0。

输出

对于每个测试点,对应的结果输出一行,表示最少用多少次指令即可完成所有的画线。

样例输入

2
4
3 8 6 8
-3 8 1 8
2 3 4 5
3 4 6 7
5
1 1 2 2
2 2 3 3
3 3 4 2
4 2 5 1
1 0 100 0

样例输出

3
3

2 收藏


直接登录