Ignatius 被魔王抓走了，有一天魔王出差去了，这可是Ignatius逃亡的好机会。
魔王住在一个城堡里，城堡是一个 $A*B*C$ 的立方体，可以被表示成 $A$ 个 $B*C$ 的矩阵。
刚开始 Ignatius 被关在 $(0,0,0)$ 的位置，离开城堡的门在 $(A-1,B-1,C-1)$ 的位置。
现在知道魔王将在 $T$ 分钟后回到城堡，Ignatius 每分钟能从一个坐标走到相邻的六个坐标中的其中一个。
现在给你城堡的地图，请你计算出 Ignatius 能否在魔王回来前离开城堡，只要走到出口就算离开城堡，如果走到出口的时候魔王刚好回来也算逃亡成功。如果可以请输出需要多少分钟才能离开，如果不能则输出 -1。

第一行是一个正整数 $K$，表明测试数据的数量。
每组测试数据的第一行是四个正整数 $A,B,C,T\ (1\leq A,B,C\leq 50,\ 1\leq T\leq 1,000)$，它们分别代表城堡的大小和魔王回来的时间。
然后是 $A$ 块输入数据（先是第 $0$ 块，然后是第 $1$ 块，第 $2$ 块......），每块输入数据有 $B$ 行，每行有 $C$ 个正整数，代表迷宫的布局。其中 $0$ 代表路，$1$ 代表墙。

对于每组测试数据，如果 Ignatius 能够在魔王回来前离开城堡，那么请输出他最少需要多少分钟。否则输出 $-1$。