Circles and Ray

Problem

2次元平面上にそれぞれ互いに共通部分をもたない N 個の円が与えられる。 また、円にはそれぞれ1から N までの番号が割り振られている。

あなたは、端点が1番目の円の円周上にあるような半直線を任意の数だけ設置することができる。 どの円も1本以上の半直線との共通部分を持っているようにするためには、最低何本の半直線を設置しなければならないかを求めなさい。

Input

入力は以下の形式で与えられる。

N
x1 y1 r1
x2 y2 r2
...
xN yN rN

1行目に、1つの整数 N が与えられる。 2行目からの N 行のうち i 行目には i 番目の円のx座標、y座標、半径を表す3つの整数 x_i, y_i, r_i が空白区切りで与えられる。

Constraints

• 2 ≤ N ≤ 16
• -100 ≤ x_i ≤ 100 (1 ≤ i ≤ N)
• -100 ≤ y_i ≤ 100 (1 ≤ i ≤ N)
• 1 ≤ r_i ≤ 100 (1 ≤ i ≤ N)

Output

どの円も1本以上の半直線との共通部分を持っているようにするためには最低何本の半直線を設置しなければならないかを出力せよ。

Sample Input 1

3
0 0 2
3 3 1
6 1 1

Sample Output 1

1

Sample Input 2

4
1 2 3
12 2 2
7 6 2
1 9 3

Sample Output 2

2

Sample Input 3

5
0 0 5
0 10 1
10 0 1
-10 0 1
0 -10 1

Sample Output 3

4

Note

Link

 

---