题目描述

小青正在玩一个营救游戏。游戏地图是一个由0和1组成的网格，0表示可以通行的道路，1表示障碍物。小青需要从起点走到终点，每次只能向上、下、左、右四个方向移动一步，且不能走出网格边界，也不能进入障碍物。请你帮助小青计算从起点到终点的最短路径长度。

输入格式

第一行一个整数 n，表示数据组数，接下来若干行数据（1 ≤ n ≤ 10000）

输出格式

输出一行一个整数，表示计算结果

样例

输入 # 1

3
001
101
100
1 1 3 3

输出 # 1

4