题目描述

CF（Construct Foothill）是一款模拟经营类型的游戏。玩家将扮演一位建筑师，对一块山麓地区进行景区建设。

一块山麓地区由一块 $n \times m$ 的区域（$n$ 行 $m$ 列）表示，其中，每块区域 $(i,j)$ 都有一个高度 $a_{ij}$。对于游客而言，他们每步只能走到相邻的区域。游客不喜欢费力的旅行，所以他们只会从高的区域到低的区域（不走“低到高”）。并且作为崎岖的山区，没有两个地区有相同的高度。但寸土寸金，如果游客能多到达一块区域，就能多赚一大笔钱。老板得知后，命令你建设这个山区成为景区，并且所有区域都能从入口到达，否则不给发工资。

作为建筑师，你可以建设传送器来帮忙克服游客的困难。传送器可以搭建在任意区域，但传送器相当昂贵，一个要 234 元。为了确保传送的稳定性，并预防不同地区电磁干扰，如果要开通两个传送器之间的传送线路，还需要一定的建设成本。设在 $(x_1,y_1)$ 与 $(x_2,y_2)$ 之间搭建传送线路的价格为：

$114 | x_1 - x_2 |+ 5141 | y_1 - y_2 |+ 919810$$|a_x-a_y|$

其中 $a_x$、$a_y$ 分别表示这两个区域的高度（即各自所在格子的 $a$ 值）。

已知所有游客都从左上角 $(1,1)$ 作为景区入口，而且老板在入口免费帮你建了一个传送器。希望所有游客都能从入口到达这个景区的任意一个区域。你想要尽可能减少成本，又要完成老板的指标，求最少需要花多少钱。

行走规则：只能在相邻格之间行走，且必须满足“从高到低”。

输入格式

每个测试包含多个测试用例。

• 第一行包含测试用例的数量 $t$（$1 \le t \le 20$）。
• 对于每个测试用例：
  • 第一行两个整数 $n,m$（$1 \le n \le 100,\ 1 \le m \le 100$）。
  • 接下来 $n$ 行，每行 $m$ 个整数，第 $i$ 行第 $j$ 个数为 $a_{ij}$（$1 \le a_{ij} \le 10000$）。

输出格式

对每个测试用例，输出一个整数，表示完成任务的最小成本。

样例

输入

2
2 2
1 2
3 4
2 3
1 5 4
2 3 6

输出

17182633869
34364347814