And Then. How Many Are There?

時間制限 : 8 sec, メモリ制限 : 65536 KB
英語版はこちら

そして,いくつになった?

有名な一人遊びゲームの作家であるソリタリウス氏は,今日もまた新しいアイデアを思いついた. ソリタリウス氏の新しいゲームでは,さまざまな色と大きさの平らな円盤を使う.

まず最初に,全部の円盤をテーブル中央付近にばらまく. 別の円盤が上に重なっていない円盤の中に同じ色のものが2枚あれば,それらを同時に取り除くことができる. なお,円盤同士が1点で接しているだけなら,それらを重なっているとはみなさない.



図 D-1: テーブル上の7枚の円盤

たとえば,図 D-1 の場合,まず最初に取り除けるのは2枚の黒い円盤だけである. これらを取り除くことで,今度は2枚の白い円盤を取り除けるようになる. しかし,グレーの円盤は決して取り除くことができない.

この問題では,与えられた円盤の色,大きさ,初期の位置関係から,最大何枚の円盤を取り除くことができるか計算するプログラムを作成して欲しい.

Input

入力は複数のデータセットからなり,それぞれが以下のような形式でテーブル上に円盤をばらまいた直後の状態を表す.

n
x1 y1 r1 c1
x2 y2 r2 c2
...
xn yn rn cn

最初の行のnは円盤の枚数を表す正整数である. 続くn行は,それぞれが空白文字1個で区切られた4個の整数からなり,n枚の円盤の色,大きさ,初期の位置関係を次のように表す.

  • (xi, yi), ri, cii番目の円盤の中心のxy座標,半径,色番号をそれぞれ表し,
  • i番目の円盤がj番目の円盤の上に重なるときには,必ずi < jが成り立つ.

色番号は1以上4以下であり,一つのデータセット中に同じ色の円盤は高々6枚しか出現しないと仮定して良い. また,円盤の中心のxy座標は常に0以上100以下,半径は常に1以上100以下と仮定して良い.

入力の終わりは1個のゼロで示される.

Output

各データセットについて,取り除ける円盤の最大枚数をそれぞれ1行に出力しなさい.

Sample Input

4
0 0 50 1
0 0 50 2
100 0 50 1
0 0 100 2
7
12 40 8 1
10 40 10 2
30 40 10 2
10 10 10 1
20 10 9 3
30 10 8 3
40 10 7 3
2
0 0 100 1
100 32 5 1
0

Output for the Sample Input

2
4
0

Source: ACM International Collegiate Programming Contest , Japan Domestic Contest, Tokyo, Japan, 2011-06-24
http://icpc2011.ait.kyushu-u.ac.jp/