最近seventh沉迷于4399，他发现了一个好玩的游戏，吃金币，这个游戏的你通关的越快，评分越高，seventh想知道，最快通关时间是多少。
游戏规则如下：
1、游戏地图大小为n*m,即n层，每层m个格子。
2、游戏人物从地图的左下角开始行动。
3、通关条件为吃光所有的金币。
4、游戏人物只有在每一层的最左边或最右边才能向上移动，否则只能左右移动，不能下去。
5、每次移动需要花费一个单位的时间。
第一行包含一个整数T，表示有T组数据。(T<=100)
接下来T组
每组数据第一行有两个整数n和m(1<=n<=15,3<=m<=100)
接下来n行每行m个字符，0代表那个位置没有金币，1代表那个位置有金币
注意：地图从上向下给出
对于每组数据输出一个整数，为最快完成游戏的时间
4 2 4 0010 0100 3 6 001000 000010 000010 4 5 01110 01110 01110 01110 3 4 0000 0100 0100
5 12 18 4