Description

太空中有n 类卫星（即类型1、类型2…）共m个。对于满足1<=i<=n的任意整数i，类型i的所有卫星共同保卫着包含它们的最小凸多面体（即凸包。可能会退化，即体积为0）。如果空间中一个点被至少k 类卫星保护，我们说这个点属于安全区域。

你的任务是计算所有安全区域的总体积。

Input

输入第一行为数据组数T (T<=25)。每组数据第一行为三个整数n, k和m(1<=k<=n<=5, 4<=m<=50)。

以下m 行每行包含一个整数t 和三个 实数 x, y, z，表示一个类型t 的卫星，坐标为(x,y,z)(1<=t<=n, 0<=x,y,z<=10)。 每组输入数据后有一个空行。

注意：评测数据（而非样例数据）中卫星坐标都是随机生成的。

Output

对于每组数据，输出安全区域的总体积，四舍五入保留小数点5位。

2
2 1 16
1 0 0 0
1 0 0 2
1 0 2 0
1 0 2 2
1 2 0 0
1 2 0 2
1 2 2 0
1 2 2 2
2 1 1 1
2 1 1 3
2 1 3 1
2 1 3 3
2 3 1 1
2 3 1 3
2 3 3 1
2 3 3 3

1 1 4
1 0 0 0
1 0 1 0
1 0 0 1
1 1 0 0

15.00000
0.16667