Jhadgre在生日那天收到了一张神秘的藏宝图，于是他决定和Wpremig分享这张藏宝图，并且去寻宝！
这张藏宝图上总共有N行，每行有M个格子，共N*M个格子，每个格子上写了一个数字。
藏宝图上写了一段字：神秘的有缘人啊，这些格子已经被其他人挖过了，我已经替你标出了所有格子被挖到的深度，并且在这个宝藏上加了一个魔法，只要你把所有格子都挖到同一个深度，宝藏自然就会出现。
这看似是一个很简单的问题，只要知道现在最深的那个格子，其他格子都挖到这个深度，就是最快的方式了。然而Wpremig和Jhadgre却发现，还有一句话：我知道你们有两个人，所以你们在挖的时候必须两个人同时各挖一个格子，并且这两个格子必须相邻！
这就比较尴尬了，Wpremig和Jhadgre很不高兴，这是送礼呢还是膈应人呢？不挖了！
虽然这样说，但是人总是会遵循“真香定理”。在几天后Wpremig和Jhadgre还是决定去挖宝藏，现在他们在出发前想知道，最少需要挖多少次才能获得宝藏呢？（假设每次一个人挖一个格子可以将这个格子的深度+1）
第一行一个整数T表示数据组数（T<=10）
对于每组数据，第一行两个整数N,M。
接下去N行每行M个整数。
保证 T<=10，1<=N,M<=40，所有数为正整数且小于1000000000
对于每组数据输出最少的挖掘次数，若无论如何都不能获得宝藏，则输出-1；