有时候，做人不能太斤斤计较。社会上讲究一个让步和妥协，大家都得给自己和对方留一些余地。所以有时候不必太追求精确，毛估估就行。

俗话说得好，“退一步海阔天空”，本题的出题人也想和大家和平相处。本着给选手多送分的原则，这道题你不必求出精确解，毛估估求一下就行啦！如果你的答案和精确值差不多，出题人会假装没看出来区别然后给你满分的！

那么接下来描述这个送分题的题面：有一张 $n$ 个点的无向无权连通图，$q$ 次查询两点之间的最短路长度。但正如前面所说的，只要你与答案差不超过 $1$，即如果最短路长度是 $d$，输出 $d-1,d,d+1$ 之一时，出题人都会假装你算的是对的。

这时候大家可能会问了，这不是普及组题目吗？我刚学 OI 的时候就做过了！所以出题人决定加大题目的数据范围，但这下出题人都不会做了。不过，你会吗？

输入格式

为了减小输入量，本题对输入进行了压缩。

第一行两个正整数 $n,q$，表示图的点数和询问次数。

接下来 $n-1$ 行，第 $i$ 行为一个长度为 $\lceil \frac{i}{4}\rceil$ 的字符串，仅包含 '0' ~ '9' 和 'A' ~ 'F'。这里，字符 '0'~'9' 依次对应整数 $0\sim 9$，'A'~'F' 依次对应整数 $10\sim 15$。

对 $\mathrm{\forall }1\le j\le i$，$G$ 中边 $(j,i+1)$ 存在当且仅当该字符串第 $\lceil \frac{j}{4}\rceil$ 个字符所对应整数的二进制表示下从低往高第 $(j-1)mod4$ 位为 $1$，注意若 $imod4\ne 0$，则最后一个字符二进制表示下没有定义的位一定为 $0$。

接下来 $q$ 行，每行两个正整数 $x,y(1\le x,y\le n)$，表示一次询问。

输出格式

$q$ 行，每行一个整数，表示毛估估求出的答案。如果精确答案为 $d$，输出 $d-1,d,d+1$ 均算作正确答案。

样例一

input

4 3
1
1
5
1 2
2 3
3 4

output

1
2
1

explanation

边集为 $(1,2),(1,3),(1,4),(3,4)$。

注意这里的样例输出给的是精确答案，很多其他输出也会被认为是正确答案，如 $1,3,0$。

数据范围

对于所有数据，保证 $2\le n\le 8000,1\le q\le {10}^6$。

特殊性质 A：每条边 $(i,j)(1\le i<j\le n)$ 以 $\frac{1}{2}$ 概率出现。

时间限制：$3\mathtt{\text{s}}$

空间限制：$1\mathtt{\text{GB}}$

提示

请选手相信自己算法的常数与评测机的效率。