Description

lcs有N x M的数字矩阵，现在，他想通过数次矩阵移动操作以获得一个左上角值为X的矩阵。 矩阵移动共有四种：向左、向右、向上、向下。以向上为例：对于1..N-1行，向上移动一行，对于第0行，移动到第N-1行。其他三种移动类似。具体请见下图：

现在给你一个数字矩阵，请求出最少需要几步移动才能满足lcs的条件。

Input

第一行是case个数T。接下来T组数据，每组先是一行矩阵的大小N和M(1<= N <= 50,1 <= M <= 50)，然后是NxM的数字矩阵(数字在0~9之间)，最后是X(0 <= X <= 9)。

Output

输出满足lcs的条件的最小移动步数。如果不存在，输出-1。

Sample

Input

2
4 3
136
427
568
409
2
1 2
12
0

Output

2
-1

Source: LCS