問題文

縦 H マス、横 W マスのグリッドがあります。上から i 行目、左から j 列目のマスを (i, j) とします。 各マス (i,j) には、そのマスにブロックが配置される時刻を表す整数 A_{i,j} が書かれています。

時刻は 1 から K = \max(A_{i,j}) まで進みます。配列 A は以下の性質を満たします。

• 1 \leq k \leq K を満たす任意の整数 k について、A_{i,j} = k となるマスが少なくとも 1 つ存在する。
• 同じ値 k を持つマスの集合は、上下左右に連結している。
• ブロックは各列で下から順に積まれる。すなわち、任意の 1 \leq i \leq H-1 と 1 \leq j \leq W に対して A_{i+1, j} \leq A_{i, j} が成り立つ。

ある時刻において、列 j に積み上がっているブロックの個数を h_j とします。初期状態ではすべての列で h_j = 0 です。

soryuusi 君は初期状態において列 s にいます。 時刻 k = 1, 2, \dots, K に対して、順に以下のようにゲームが進行します。

1. soryuusi 君の移動：soryuusi 君はグリッド内の左右に隣接する列へ 1 列ずつ、任意の回数だけ移動することができる（移動せず現在の列に留まることも可能である）。 列 x から隣接する列 y へ 1 列移動するごとに、その時点でのブロックの高さを用いて |h_x - h_y| + 1 のスタミナを消費する。
2. ブロックの配置：A_{i,j} = k となるすべてのマスにブロックが配置され、該当する列の h_j が配置されたブロックの個数分だけそれぞれ増加する。 このとき、soryuusi 君が現在いる列に 1 つでも新たにブロックが配置された場合、soryuusi 君は押し潰されてゲームオーバーとなる。

時刻 K のブロックの配置が終了するまで soryuusi 君がゲームオーバーにならずに生き残ることができるか判定し、可能な場合は消費するスタミナの合計の最小値を求めてください。生き残ることが不可能な場合は -1 を出力してください。

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

• 1 \leq T \leq 10^5
• 1 \leq H, W
• H \times W \leq 5 \times 10^5
• 1 \leq s \leq W
• 1 \leq A_{i,j} \leq H \times W \ (1 \leq i \leq H, 1 \leq j \leq W)
• 1 \leq k \leq K を満たす任意の整数 k について、A_{i,j} = k となるマス (i,j) が少なくとも 1 つ存在する
• A_{i,j} = k となるマス (i,j) の集合は、上下左右に連結している
• A_{i+1, j} \leq A_{i, j} \ (1 \leq i \leq H-1, 1 \leq j \leq W)
• すべてのテストケースについての H \times W の総和は 5 \times 10^5 以下
• 入力される数値はすべて整数

入力例 1

3
3 4 1
3 3 3 2
3 1 2 2
1 1 1 2
2 3 2
2 2 3
1 2 2
4 5 5
16 17 18 19 20
11 12 13 14 15
6 7 8 9 10
1 2 3 4 5

出力例 1

10
-1
8

1 つ目のテストケースについて、soryuusi 君は以下のように行動することで、消費スタミナ 10 を達成できます。

• 4 列目に移動する。(|0 - 0| + 1) + (|0 - 0| + 1) + (|0 - 0| + 1) = 3 のスタミナを消費する。
• 時刻 1 のブロックが配置される。
• 2 列目に移動する。(|0 - 1| + 1) + (|1 - 2| + 1) = 4 のスタミナを消費する。
• 時刻 2 のブロックが配置される。
• 4 列目に移動する。(|2 - 2| + 1) + (|2 - 3| + 1) = 3 のスタミナを消費する。
• 時刻 3 のブロックが配置される。

消費スタミナ 9 以下で生き残ることは不可能なので、消費スタミナの最小値は 10 です。

2 つ目のテストケースについて、soryuusi 君はどのように行動しても、時刻 2 のブロックの配置を回避することはできません。したがって、このテストケースに対する出力は -1 となります。