Description

题目描述：

在平面上有许多线段，其中一些平行于y轴且在x轴上的间距相等（均为100），起始y坐标都是0，终止y坐标都是32767，称作第一类线段，把这些线段按照x坐标从小到大编号0，1 … n1-1，第二类线段与y轴不平行，而且起点和终点在不同的两条第一类线段上，两条线段最多有一个交点（没有重合或部分重合的情况），第三类线段是第二类线段被第一类线段切割所成的小线段，如下图：

任务描述：

给出所有线段的描述，求出满足以下条件的第三类线段对的个数：两个线段有在非端点处有交点。

Input

第一行是一个正整数num,表示测试数据的组数，下面是num组测试数据。

每组测试数据的第一行是两个正整数n1, n2表示第一类和第二类线段的个数（2<=n1<=16,0<=n2<32768），下面有n2行，每行描述一条第二类线段，有四个正整数k1 p1 k2 p2，k1和k2分别表示此线段的起点和终点所在的第一类线段的编号，p1和p2分别表示此线段起点和终点的y坐标（0<=p1，p1 < 32768 ）。

Output

对每组测试数据输出一行，一个正整数n，表示满足条件的线段对的个数。

2
2 5
0 1 1 4
0 3 1 1
0 4 1 5
0 5 1 4
0 6 1 4
4 8
0 0 2 2
0 1 2 3
0 3 2 1
0 3 3 2
1 0 3 2
1 3 2 0
2 0 3 1
2 3 3 0

3
10

Source

qinlu@POJ