题号：NC21722
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
上班族的三上悟在道路上被歹徒给刺杀身亡后，回过神来发现自己转生到了异世界,并成为了一只萌萌的史莱姆，并被暴风龙维鲁德拉取名为利姆鲁。
作为故事的主人公，并且是转生者，利姆鲁也有独特的金手指——大贤者和捕食者（两个技能）。
这两个技能的效果如下：
为了拯救静，利姆鲁决定勇闯迷宫！
作为故事的主人公，并且是转生者，利姆鲁也有独特的金手指——大贤者和捕食者（两个技能）。
这两个技能的效果如下：
捕食者
捕食：将对象物吸入体内。不过，对象仍保有意识时，成功率将大幅减低。发动对象不限于有机物或无机物，也包括技能及魔法。
解析：能解析、研究吸收对象，生成制作可能之道具。物质条件备齐时，亦能进行复制。成功解析术式后，有机会学习对象技能、魔法。
胃袋：收纳捕食对象。此外，亦能保管解析后生成的物质。收纳进胃袋后将不受时间影响。
拟态：能重现吸收对象，行使同等能力。不过，只限成功解析情报的对象物。
隔离：收纳无法解析的有害效果，将其净化后还原成魔力。
大贤者
思考加速：将知觉速度提升至千倍。
解析鉴定：解析对象物，进行鉴定。
并列演算：能将欲解析的事物与思考区隔开来进行演算。
咏唱排除：行使魔法等技能时，无须咒文咏唱程序。
有一天，利姆鲁在这个世界最重要的人静被魔王带走，并将其困在一个n*n的迷宫内的某一处，迷宫的每个格子都可能有一只魔物，魔物的攻击力为a[i][j]，因而利姆鲁只有当攻击力大于等于a[i][j]才能通过这个方格，否则就只能绕道（只能朝上下左右四个方向）而行。为了拯救静，利姆鲁决定勇闯迷宫！
现在利姆鲁站在（sx，sy）处，静在（ex，ey）处，为了保证自己能够成功拯救静，利姆鲁在初始时靠捕食者将自己的攻击力提升到x后才出发，但是由于时间紧急（利姆鲁不想和静分开太久），使用捕食者需要花费时间，所以利姆鲁想知道能够成功救出静的最小的x（默认初始位置的魔物对利姆鲁无攻击，即此位置对其而言是安全位置）是多少。
输入描述:
第一行为一个正整数t（1<=t<=20)，表示测试数据的数量。
每组数据第一行为一个正整数n（1<=n<=500)，表示迷宫大小。
第2行至第n+1行，每行有n个整数，相邻两个数用空格隔开。第i行第j列的数a[i][j]表示这一个方格中的魔物的攻击力大小为a[i][j]（0<=a[i][j]<=1e5)。
第n+2行为四个正整数sx，sy，ex，ey（相邻两个数用空格隔开），分别表示利姆鲁的坐标和静的坐标。(1<=sx，sy，ex，ey<=n)。
输出描述:
利姆鲁初始的攻击力的最小值x（大于等于0的整数）。