如图，在时空中有一些时空乱流（灰色区域或理解成墙）。时空乱流平行于X轴，宽度为一个单位，但长度各不相同，并且同一区域上不会有两个时空障碍。现在要求从上方沿Y轴方向，走到下方。途中可以穿越部分时空乱流，但会消耗一部分魔法力，所以穿越数有限帛，不能超过一个值k。
现在从X轴上的哪一个点出发，都能走到下方，必须湮灭多少时空乱流，使得每条路上的时空乱流数都不超过穿越的限定值。
例如，如图当穿越限定值k=3时，除了X轴为6的点外，可以从X轴上的任何一点出发。

输入有多组数据，第一行为组数t(1<=t<=10)，随后是每组测试数据，第一行为两个整数n(1<=n<=100)，表示时空乱流的数，和穿越限定值k(1<=k<=100),以下n行表示时空乱流的起始坐标和结束坐标。

每组一行数据，表示最小湮灭的时空乱流数。

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

1
1