AT_ttpc2023_d Spacecraft

$ 3 $ 次元空間上の相異なる座標に $ N $ 個の星が輝いています。 $ i $ 番目の星は点 $ P_i(x_i,y_i,z_i) $ に存在します。また、半径 $ R $ の球状の宇宙船が原点を中心に浮かんでいます。 空間上の点 $ p $ が **素敵な点** であるとは、 $ i = 1, 2, \dots, N $ に対して次の条件が同時に成り立つことを言います。 - 点 $ p $ から $ i $ 番目の星が観測できる。すなわち、 $ p $ と $ P_i $ を端点とする線分が宇宙船の周及び内部を通らない。 素敵な点が存在する領域の連結成分の個数を求めてください。すなわち、素敵な点全体の集合を $ L $ としたとき、 $ L $ を以下の同値関係 $ \sim $ で割ったときの商集合の大きさを求めてください。 - $ p_1, p_2 \in L $ に対し、 $ p_1 $ と $ p_2 $ を端点とする $ L $ 上の曲線が存在するとき、かつそのときに限り $ p_1 \sim p_2 $ である。 なお、この値は $ 10^{18} $ 以下の整数になることが証明できます。 $ T $ 個のテストケースが与えられるので、それぞれについて答えてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ 各テストケース $ \mathrm{case}_i $ は以下の形式で与えられる。 > $ N $ $ R $ $ x_1 $ $ y_1 $ $ z_1 $ $ \vdots $ $ x_N $ $ y_N $ $ z_N $

答えを出力せよ。

### Sample Explanation 1 $ 1 $ つめのテストケースでは、素敵な点が存在します。 - 例えば $ (0,0,100) $ は素敵な点です。この点と与えられた $ 4 $ 点のうちどの点と結んだ線分も、宇宙船の内部を通りません。 - 他にも $ (21,0,0) $ は素敵な点です。 - これらの $ 2 $ 点は同じ連結成分に属しています。 $ 2 $ つめのテストケースでは、素敵な点が存在しません。 ### Constraints - 入力はすべて整数 - $ 1\le T\le 10 $ - $ 1 \le N \le 500 $ - $ 1 \le R \lt \sqrt{x_i^2+y_i^2+z_i^2} \le 10^3 \ (1\le i\le N) $ - $ (x_i,y_i,z_i) \neq (x_j,y_j,z_j)\ (1 \le i < j \le N) $ - 以下の操作によって答えは変わらない - $ i=1,2,\dots ,N $ について、原点を通る直線 $ l_i $ と実数 $ \theta _i\ (|\theta _i|\le 10^{-6}) $ をそれぞれ独立に選ぶ。星 $ i $ の位置を $ l_i $ を軸に角度 $ \theta _i $ だけ回転させた位置に移動させる。