C - RPG

配点 : 300点

縦 行、横 列のグリッドがあります。上から 行目、左から 列目のマスを とします。
またこのグリッドでは端を越えて移動すると反対側に出てくる、つまりグリッドは端から端まで循環します。
スタート地点の座標は であり、ゴール地点の座標は です。
くしらくんは以下の2種類の操作を行ってスタート地点からゴール地点へたどり付きたいです。

• コストを 払い、隣へ1マス移動する。
  厳密には、今いる座標を として、コストを 払って のいずれかに移動する。
• コストを払い、斜めへマス移動する。
  厳密には今いる座標を として、コストを 払って のいずれかに移動する。

くしらくんが目標を達成するために必要なコストの最小値を答えてください。 個のテストケースが与えられるのでそれぞれに答えてください。

※追記(13:34) 厳密に書いた式が間違っています。0-indexであるものにその式を適用してください。

• 入力はすべて整数

入力は以下の形式で標準入力から与えられる。

各テストケースは以下の形式で与えられる。

行出力してください。 行目には、 に対する答えを出力してください。

• 入力

3
3 6 1 2 3 4
3 3 1 1 2 3
314 159 26 53 98 97

• 出力

5
3
188

1つめのテストケースでは以下のように移動することで目標を達成することができます。

• コストを 払って右へ移動する。
• コストを 払って右上へ移動する。

よりも小さいコストで目標を達成することが出来ないので を出力します。