Circle Artwork

Time limit1sMemory limit128 MB

Summary

Given up to 100 colored points, count how many colors have a circle through two of their points that contains no point of another color.

Level: Hard8 of 10
Topics: Geometry, Brute force, Sorting, Implementation
Solved: No attempts yet

Problem

The circle is an ancient and universal symbol of unity, wholeness, and infinity. Playing the role of a modern artist, we want to compose a painting from colored points and circles.

First we place several colored points on the canvas. For each color $C_i$ we would like to draw one circle that satisfies both of the following conditions:

every colored point lying inside the circle or on its boundary has color $C_i$ ;
at least two colored points lie on the boundary of the circle.

Since a point on the boundary is a point "inside or on the boundary", any boundary point must itself have color $C_i$ . Hence a valid circle for color $C_i$ passes through at least two points of color $C_i$ and contains no point of any other color, neither strictly inside nor on the boundary. Points of color $C_i$ may lie inside, on, or outside the circle. For some colors no such circle exists.

Given the colored points, determine the largest number of colors for which such a circle exists — that is, how many colors admit at least one valid circle.

Input

The input contains several test cases. Each test case begins with a line containing a single integer $n$ ( $1 \le n \le 100$ ), the number of colored points. Each of the next $n$ lines has the form C X Y, where C is the color of the point (a string of at most $20$ lowercase English letters) and $X$ , $Y$ are its integer coordinates with $-1{,}000{,}000 \le X, Y \le 1{,}000{,}000$ .

The input ends with a line containing a single $0$ .

Output

For each test case, print a single line containing the largest number of colors for which a valid circle exists.

Examples5

Example 1

Input

4
red 1 1
blue 1 2
blue 3 2
yellow 3 3
0

Expected output

Example 2
Input
```
2
green 0 0
green 10 0
0
```
Expected output
```
1
```

Example 3

Input

4
red 0 0
red 0 2
blue 100 100
blue 100 102
0

Expected output

Example 4
Input
```
3
a 0 0
a 4 0
b 2 0
0
```
Expected output
```
0
```
Example 5
Input
```
2
x 0 0
x 5 0
2
y 0 0
z 1 0
0
```
Expected output
```
1
0
```