#P18165. Henry the Plumber

Henry the Plumber

Henry the Plumber

Henryk 需要完成若干三维水暖工程。每个工程要把进水口与出水口连接起来,使用若干直管和弯头。弯头把两段管道以直角连接。进水口处必须按给定方向安装第一个弯头,出水口处必须按给定方向安装最后一个弯头。

进水口与出水口的方向都是水平的(zz 坐标为 0)。

为简化问题,进水口、出水口与所有弯头都是 R3\mathbb{R}^3 中的点,管道是零宽度的线段。

进水口与出水口位于不同位置。第一段管道必须从进水口出发,且垂直于进水口方向;之后每段管道必须从上一条管道的末端出发,并与它垂直;最后一段管道必须垂直于出水口方向,并终止于出水口。每段管道长度为正。

管道除在弯头处相接外不能相交:所有弯头必须位于不同点,不能落在任何管道内部,管道之间除公共弯头外不能有公共点。

进水口和出水口处的弯头也计入总数。

对每个工程,判断能否完成;若能,求所需的最少弯头数。

输入格式

第一行一个整数 tt(1≤t≤1001\le t\le100)。

每个工程四行:

  • 三个整数 x1,y1,z1x_1,y_1,z_1(−20≤xi,yi,zi≤20-20\le x_i,y_i,z_i\le20),表示进水口;
  • 两个整数 p1,q1p_1,q_1(−20≤pi,qi≤20-20\le p_i,q_i\le20,(p1,q1)≠(0,0)(p_1,q_1)\ne(0,0)),表示进水口方向;
  • 三个整数 x2,y2,z2x_2,y_2,z_2,表示出水口;
  • 两个整数 p2,q2p_2,q_2,表示出水口方向。

水沿 (p1,q1,0)(p_1,q_1,0) 方向水平流入(即来自 (x1−p1,y1−q1,z1)(x_1-p_1,y_1-q_1,z_1));沿 (p2,q2,0)(p_2,q_2,0) 方向水平流出(即流向 (x2+p2,y2+q2,z2)(x_2+p_2,y_2+q_2,z_2))。

保证进水口与出水口不同。

输出格式

输出 tt 行,每行一个整数表示最少弯头数,或 NIE 表示无法完成。

样例

输入:

2
-1 -1 3
1 1
2 2 3
2 2
5 5 1
3 0
7 6 -2
1 -2

输出:

4
3

样例解释:第一个工程的最优方案需要四个弯头,例如依次安装在 (-1,-1,3),(-2,0,3),(1,3,3),(2,2,3):

第一个工程的四弯头最优方案,含原图坐标与水流箭头

一个较差的六弯头方案是 (-1,-1,3),(-2,0,3),(-1,1,4),(1,-1,4),(3,1,4),(2,2,3):

第一个工程的六弯头方案

第二个工程可以在 (5,5,1),(5,5,-2),(7,6,-2) 安装三个弯头:

第二个工程的三弯头最优方案