Circles and Ray

Problem

N circles are given on the two-dimensional plane, each of which has no intersection. In addition, each circle is assigned a number from 1 to N.

You can place any number of half-lines such that the endpoints are on the circumference of the first circle. Find out how many half lines must be installed in order for each circle to have an intersection with one or more half lines.

Constraints

• 2 ≤ N ≤ 16
• -100 ≤ xi ≤ 100 (1 ≤ i ≤ N)
• -100 ≤ yi ≤ 100 (1 ≤ i ≤ N)
• 1 ≤ ri ≤ 100 (1 ≤ i ≤ N)

Input

The input is given in the following format.

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

The first line is given one integer N. Of the N lines from the second line, the i-th line is given three integers xi, yi, and ri representing the x-coordinate, y-coordinate, and radius of the i-th circle, separated by blanks.

Output

Output at least how many half lines must be installed so that each circle has an intersection with one or more half lines.

Examples

Input

3 0 0 2 3 3 1 6 1 1

Output

1

Input

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

Output

2

Input

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

Output

4

inputFormat

Input

The input is given in the following format.

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

The first line is given one integer N. Of the N lines from the second line, the i-th line is given three integers xi, yi, and ri representing the x-coordinate, y-coordinate, and radius of the i-th circle, separated by blanks.

outputFormat

Output

Output at least how many half lines must be installed so that each circle has an intersection with one or more half lines.

Examples

Input

3 0 0 2 3 3 1 6 1 1

Output

1

Input

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

Output

2

Input

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

Output

4

样例

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

4