You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

🐂大哥作为一名间谍，他成功混入了ACM实验室，并夺得了一块xcpc的金牌。但同时🐂大哥也触发了警报，现在他需要尽快逃离ACM实验室

Description

🐂大哥可以向上下左右四个方向瞬移，每一次瞬移只能传送2的幂的距离，并且在瞬移的路径上不能有障碍物

ACM实验室整体是一个n*m的矩形，而🐂大哥现在正处于（1,1）坐标，而出口在（n,m）坐标

求🐂大哥至少要瞬移几次才能到达出口，由于ACM实验室可能在警报中启动部分障碍物，所以当🐂大哥无法抵达出口时输出"hiahia~"

Format

Input

第一行两个正整数n和m，10<n,m<2e3

接下来n行，每行m个数字，数字只由0或1组成，其中0代表无障碍物，1代表有障碍物

Output

一个整数，表示抵达出口的最少的瞬移次数，如果无解输出"hiahia~"

Samples

8 3
0 1 1 
0 0 0 
1 0 0 
0 0 0 
0 0 0 
0 1 0 
0 0 0 
1 1 0 

4

Limitation

1s, 1024KiB for each test case.