小w高考之后，为了和同学出去旅游，想要知道每个城市两两之间的最短距离。

小w生活的国家，是一个有$n$个城市的小国，城市之间有$m$条权值为$1$的无向边相连。

小y一眼就看出来这是一个经典的多最短路问题，不过因为小w并不是一个斤斤计较的人，他只想知道大致的距离。

如果两点间距离为$d$，那么输出$d$, $d + 1$或者$d + 2$，都算正确。

聪明的你能帮助小w规划他的旅行吗？

为了加速输出，小w只会询问$q$对点之间的距离。

输入格式

一行两个整数$n, q$。

之后$n$行，每行一个长度为$n$的01串。输入一个01矩阵。

$A_{i,j} = 1$表示$i$和$j$之前有边，$A_{i,j} = 0$表示$i$和$j$之间没有边。保证矩阵是对称的，$A_{i,j} = A_{j,i}$。

接下来$q$行，每行两个整数$a, b$，表示询问$a$和$b$之间的最短路径。

输出格式

$q$行，每行输出一个答案，只要在$[ans, ans + 2]$的区间内，就算正确。如果不连通，输出$998244353$。

样例一

input

5 5
11111
11111
11111
11111
11111
1 2
1 3
2 3
4 2
5 1

output

3
1
1
2
2

数据范围

时间限制2s, 空间限制512MB