AT_kupc2016_k 百目おばけ

[problemUrl]: https://atcoder.jp/contests/kupc2016/tasks/kupc2016_k

入力は複数のテストケースからなり、以下の形式で標準入力から与えられる。 > $ T $ $ testcase_1 $ : $ testcase_T $ テストケース 1 つは以下の形式で与えられる。 > $ x_A $ $ y_A $ $ r_A $ $ x_B $ $ y_B $ $ r_B $

出力は $ T $ 行からなる。 $ i $ ($ 1\ \leq\ i\ \leq\ T $) 行目には $ i $ 番目のテストケースにおける $ S $ の要素数の最大値を出力せよ。

### あらすじ 私は召喚術を使う魔術師である。スケッチブックに描いた魔物の絵を実体化させることができる。 この度、京都大学霊長類研究所から百目おばけを召喚してほしいという依頼が届いた。 京都大学の霊長類学の発展に寄与できるなど何たる譽れであろうか！私は腕によりをかけて、飛び切り高品質な百目を作ることにした。 私はまず額と口を描いた。次はこの額と口の間になるべく多くの目を描こう。ふふ、百目の完成が楽しみだ。 ### 問題文 2 次元平面上に 2 つの円 $ A $, $ B $ がある。 円 $ A $ の中心の座標は ($ x_A $, $ y_A $), 半径は $ r_A $ であり、 円 $ B $ の中心の座標は ($ x_B $, $ y_B $), 半径は $ r_B $ である。 この 2 つの円の内部や外周は共通部分を持たない。 ここで、以下の条件を満たす円集合 $ S $ を考える。 - $ S $ に含まれる任意の円は、$ A $, $ B $ に接し、内部に共通部分を持たない。 - $ S $ に含まれる任意の異なる円 $ C_1 $, $ C_2 $ は、内部に共通部分を持たない。 集合 $ S $ の要素数の最大値を求めよ。 ### 制約 - $ 1\ \leq\ T\ \leq\ 50000 $ - $ -10^5\ \leq\ x_A\ \leq\ 10^5 $ - $ -10^5\ \leq\ y_A\ \leq\ 10^5 $ - $ -10^5\ \leq\ x_B\ \leq\ 10^5 $ - $ -10^5\ \leq\ y_B\ \leq\ 10^5 $ - $ 1\ \leq\ r_A\ \leq\ 10^5 $ - $ 1\ \leq\ r_B\ \leq\ 10^5 $ - $ {r_A}^2\ +\ {r_B}^2\