問題文

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 個のテストケースが与えられるので、それぞれについて答えてください。

制約

• 入力はすべて整数
• 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 だけ回転させた位置に移動させる。

入力例 1

3
4 12
13 0 0
0 15 0
0 -15 0
0 0 15
6 100
0 0 101
0 0 -101
0 101 0
0 -101 0
101 0 0
-101 0 0
20 333
328 -160 -572
-165 417 -847
-319 -45 271
359 -467 -625
-355 -451 658
-280 -424 687
-65 -224 573
475 -371 373
-246 -54 -903
595 -196 -305
622 -570 -250
386 -541 -566
647 455 -424
734 117 -405
830 -10 -393
-334 137 154
74 459 -92
-651 -93 -131
879 148 45
-48 126 -660

出力例 1

1
0
3

1 つめのテストケースでは、素敵な点が存在します。

• 例えば (0,0,100) は素敵な点です。この点と与えられた 4 点のうちどの点と結んだ線分も、宇宙船の内部を通りません。

• 他にも (21,0,0) は素敵な点です。

• これらの 2 点は同じ連結成分に属しています。

2 つめのテストケースでは、素敵な点が存在しません。