Randomness is ubiquitous, permeating every aspect of life. Even in crucial competitions, the key to victory often boils down to luck.

In 2035, $n$ avid fans of the game Clash Royale want to compare their skill levels. To ensure fairness, they decide to play against each other in every possible pair, for a total of $\frac{n(n-1)}{2}$ matches.

However, by that time, Clash Royale has completely evolved into "Rock-Paper-Scissors"! Therefore, in every match, the probability of either side winning is 50%, and these outcomes are mutually independent.

The losing players are naturally dissatisfied. To achieve a "spiritual victory," they introduce the concept of "indirect victory": We define $u$ as $k$-indirectly defeating $v$ if and only if there exist $k$ people $a_1, \dots, a_k$ such that $u$ defeated $a_1$, $a_1$ defeated $a_2$, $a_i$ defeated $a_{i+1}$ ($\forall i \in [1, k)$), and $a_k$ defeated $v$.

Specifically, if $u$ directly defeated $v$, it is called a 0-indirect victory.

The players have thus developed a new question: given two players $u$ and $v$, what is the minimum number of intermediate layers required to say that $u$ defeated $v$?

In other words, you need to find the minimum integer $k$ such that $u$ can $k$-indirectly defeat $v$. Since there are many dissatisfied players, you need to answer $q$ queries.

Input

Please note: The I/O volume for this problem is large. It is recommended to use fast I/O methods, such as scanf/printf in C++ or cin/cout with synchronization disabled. It is recommended to avoid languages with slow I/O.

The first line contains two integers $n, q$ ($2 \le n \le 5000, 1 \le q \le 10^5$).

The next $n-1$ lines: the $i$-th line is a binary string of length $n-i$, where the $j$-th ($1 \le j \le n-i$) digit is 1 if the $i$-th person defeated the $(i+j)$-th person, otherwise the $(i+j)$-th person defeated the $i$-th person. It is guaranteed that the win-loss relationships are generated independently and randomly, with a probability of 50% for each outcome.

The next $q$ lines: the $i$-th line contains two integers $u_i, v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$) representing the $i$-th query.

Output

Output $q$ lines, where the $i$-th line contains an integer $k$ representing the minimum $k$ such that $u_i$ $k$-indirectly defeated $v_i$. Specifically, if for any $k$, $u_i$ cannot $k$-indirectly defeat $v_i$, output -1.

Examples

Input 1

4 12
110
11
1
1 2
1 3
1 4
2 1
2 3
2 4
3 1
3 2
3 4
4 1
4 2
4 3

Output 1

0
0
1
1
0
0
1
2
0
0
1
1

Input 2

5 20
0011
001
01
1
1 2
1 3
1 4
1 5
2 1
2 3
2 4
2 5
3 1
3 2
3 4
3 5
4 1
4 2
4 3
4 5
5 1
5 2
5 3
5 4

Output 2

1
1
0
0
0
2
1
0
0
0
1
0
1
0
0
0
-1
-1
-1
-1