Hz的学弟Hh，如果有空就会抽出时间搬砖，慢慢地攒深渊票，直到有一天，Hh想验证一下自己的欧气（欧气可以理解为人品），开始疯狂得刷深渊【时间广场】，只为那一只“清泉流响”【戒指装备】。

整个深渊地图分4*6个小房间，我们这里为了简单化问题，假设每个房间都可以和上下左右的房间联通（边界除外）。【深渊地图如下】

                                            

每次刷深渊都会从左上角房间开始，一直刷到有深渊BOSS的房间，然后退出本次深渊。每刷一个房间要消耗1点疲劳。但不幸的是有些房间的难度特别高，Hh的战斗力太弱，有些房间进去了，这场深渊之旅就被迫GG（如果Hh的战斗力小于房间的战斗力，则被迫结束）。Hz学长想知道Hh每次刷深渊最少需要消耗多少点疲劳？

第一行包括一个整数类型T，表示测试数据 （ 1 <= T <= 10）

接下来的输入表示深渊地图4*6的房间，每个房间包括一个整数类型k，代表房间的难度【一般情况下难度k的取值范围 （1 <= k <= 100）, 深渊BOSS房间值为-1(深渊房间不会放在地图左上角)】。地图左上角的值就是Hh的战斗力，房间难度值为-1的为深渊BOSS房间。