Sometimes, one shouldn't be too pedantic. Society values compromise and concession; everyone needs to leave some room for themselves and others. Therefore, it is sometimes unnecessary to strive for absolute precision—a rough estimate is sufficient.

As the saying goes, "Taking a step back broadens the horizon." The problem setter also wants to live in peace with everyone. In the spirit of giving contestants more points, you do not need to find the exact solution for this problem; a rough estimate will do! If your answer is close enough to the exact value, the setter will pretend not to notice the difference and give you full marks!

Here is the description of this "giveaway" problem: You are given an undirected, unweighted, connected graph with $n$ vertices, and there are $q$ queries asking for the shortest path length between two vertices. As mentioned earlier, as long as your answer differs from the true shortest path length $d$ by no more than $1$—that is, if you output $d-1$, $d$, or $d+1$—the setter will consider your answer correct.

At this point, you might ask, "Isn't this a beginner-level problem? I solved this when I first started learning OI!" So, the setter decided to increase the constraints of the problem, but now even the setter doesn't know how to solve it. However, do you?

Input

To reduce the input size, the input for this problem is compressed.

The first line contains two positive integers $n$ and $q$, representing the number of vertices and the number of queries, respectively.

The next $n-1$ lines each contain a string of length $\lceil \frac{i}{4} \rceil$, consisting only of '0'~'9' and 'A'~'F'. Here, the characters '0'~'9' correspond to the integers $0\sim 9$, and 'A'~'F' correspond to the integers $10\sim 15$.

For all $1\leq j\leq i$, an edge $(j, i+1)$ exists in $G$ if and only if the $(j-1) \bmod 4$-th bit (from least significant to most significant) of the integer represented by the $\lceil \frac{j}{4} \rceil$-th character of the string is $1$. Note that if $i \bmod 4 \neq 0$, the undefined bits in the binary representation of the last character must be $0$.

The next $q$ lines each contain two positive integers $x, y$ ($1\leq x, y\leq n$), representing a query.

Output

Output $q$ lines, each containing an integer representing your estimated answer. If the exact answer is $d$, outputting $d-1$, $d$, or $d+1$ is considered a correct answer.

Examples

Input 1

4 3
1
1
5
1 2
2 3
3 4

Output 1

1
2
1

Note

The edge set is $(1,2), (1,3), (1,4), (3,4)$.

Note that the sample output provided here is the exact answer; many other outputs would also be considered correct, such as $1, 3, 0$.

Constraints

For all data, it is guaranteed that $2\leq n\leq 8000$ and $1\leq q\leq 10^6$.

Special Property A: Each edge $(i, j)$ ($1\leq i < j\leq n$) exists with probability $\frac{1}{2}$.

Note

Please trust the constant factor of your algorithm and the efficiency of the judge.