SP31280 ADAZOO - Ada and Zoo

瓢虫 Ada 是一位知名的农场主人。由于她在建造围栏和饲养动物方面的丰富经验，当地动物园的园长 Lichsteiner Leech 请她协助设计一个动物围场。 问题是：动物园饲养了几种非常稀有的野兽，称作 Tyg3Rs。这些 Tyg3Rs 生活在一个 **N x N** 的方形围场里，围场内的每个小方格高度各不相同。饲养员希望这些野兽能够相互嬉戏。然而，最初各个方格之间是不能互通的，但可以通过建造斜坡使任意两个相邻方格连接，每个斜坡的费用为两个方格间高度差的绝对值。 现在，动物园希望知道对于每一个 Tyg3Rs 的子集，将其所在的方格连接起来以便互通所需的最低费用。由于最终输出结果可能会相当庞大，他们只需要你计算出这些费用的总和。 作为她的好友（而且这些情况对她来说太过复杂），Ada 恳请你帮助她解决这个问题。

第一行输入一个整数 **T**，表示测试用例的个数。 每个测试用例的第一行输入一个整数 **N**，表示围场的大小。 接下来的 **N** 行中，每行有 **N** 个整数，表示每个小方格的高度。每个高度都是 0 到 1000 之间的整数。 接着的一行包含一个整数 **Q**，表示 Tyg3Rs 的数量。 随后 **Q** 行中，每行有两个整数 **x, y**，表示 Tyg3Rs 的坐标。注意，多个 Tyg3Rs 可能会同时居住在同一个方格内。

对于每个测试用例，输出连接所有 Tyg3Rs 子集的最小费用总和。

- $1 \le T \le 10$ - $1 \le N \le 50$ - $0 \le \text{高度} \le 1000$ - $1 \le Q \le 20$ - $1 \le x, y \le N$ **本翻译由 AI 自动生成**