SP1675 FUSION - Fusion Cube

博古斯公司声称已经通过设计一种进行受控聚变反应的方法解决了能源危机！该装置由边长为 $N$ 米的立方体组成，其中包含 $K$ 点电子源。每个源可以被配置为沿着对应于 $+X$ 轴、$-X$ 轴、$+Y$ 轴、$-Y$ 轴、$+Z$ 轴、$-Z$ 轴的六个可能方向中的任何一个发射电子。立方体中充满了电子以 $1m/s$ 的速度传播的介质。在时间$t = 0$ 时，所有源同时接通，沿着配置的方向发射单个电子。一个电子在直线上行进，直到它撞击立方体的边界或与另一个电子碰撞。两个电子之间的碰撞可以通过两种可能的方式发生——正面碰撞和侧面碰撞。在正面碰撞中，两个电子以相同的速度向相反的方向反弹。当碰撞的电子在相互垂直的方向上行进时，就会发生侧面碰撞。侧面碰撞后，碰撞的电子偏转 90 度，以相同的速度在相互垂直的方向上反弹，运动平面保持不变。请注意，在整个实验中，电子的运动方向保持沿其中一个坐标轴定向。如果两个以上的电子同时碰撞，则成对解决碰撞，其中任何两个碰撞电子都可以成对。为了最大限度地增加引发聚变反应的机会，我们希望最大限度地延长电子撞击立方体边界壁之前的时间。给定 $K$ 个源的位置，确定源的方向，使该时间最大化。输出此最大值。

第一行包含一个整数 $T$，即测试用例的数量 $(1 \le T \le 50)$，然后是测试用例的描述。每个测试用例的第一行包含两个整数，分别为 $K$ 和 $N$。$(1 \le K \le 1000,1 \le N \le 1000)$。其后跟随 $K$ 行，每行包含空格分隔的三个整数，表示特定源的 $X$、$Y$ 和 $Z$ 坐标。立方体对角的坐标为 $(0,0,0)$ 和 $(N,N,N)$。所有的源都将严格位于立方体内部。

对于每个测试用例，输出第一个电子在一条线上击中立方体边界之前的时间的最大值。