#arc109d. [arc109_d]L
[arc109_d]L
問題文
二次元平面上の点 に石がひとつずつ置かれています。
つの石が次の条件を満たしているとき、くの字に並んでいるといいます。
- どの石も、座標が整数である点に置かれている
- どの石も、別の石と隣接している(石からの距離が である場所に別の石が存在する)
- つの石が一直線上に存在しない
特に、最初の石の並べ方 は、くの字です。
好きな石を つ選んで好きな位置に移動させる操作を好きなだけできます。ただし、各操作後の石は、くの字に並んでいなければなりません。 できるだけ少ない操作回数で、石が点 にひとつずつ置かれている状態にしたいです。必要な操作回数は何回ですか?ただし、この状態で石がくの字に並んでいることは保証されます。この制約のもと、有限回の操作で目標を達成できます。
個のケースが与えられるので、それぞれについて答えを求めてください。
注意
つの石は互いに区別できないとします。例えば、最初に点 に置かれていた石が最終的に点 のどこに置かれていても構いません。
制約
- 点 に石がひとつずつ置かれている時、石はくの字に並んでいる
入力
入力は以下の形式で標準入力から与えられる。
各ケースは以下の形式で与えられる。
出力
個の値を出力せよ。 個目には に対応する操作回数の最小値を出力せよ。
入力例 1
出力例 1
石が置かれている場所を #
で表すことにします。 以下のように動かすと 回の操作で入力の通りの配置にできます。