有时候，做人不能太斤斤计较。社会上讲究一个让步和妥协，大家都得给自己和对方留一些余地。所以有时候不必太追求精确，毛估估就行。
俗话说得好，“退一步海阔天空”，本题的出题人也想和大家和平相处。本着给选手多送分的原则，这道题你不必求出精确解，毛估估求一下就行啦！如果你的答案和精确值差不多，出题人会假装没看出来区别然后给你满分的！
那么接下来描述这个送分题的题面：有一张 $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$。
对 $\forall 1\leq j\leq i$，$G$ 中边 $(j,i+1)$ 存在当且仅当该字符串第 $\lceil \frac{j}{4} \rceil$ 个字符所对应整数的二进制表示下从低往高第 $(j-1) \bmod 4$ 位为 $1$，注意若 $i \bmod 4\neq 0$，则最后一个字符二进制表示下没有定义的位一定为 $0$。
接下来 $q$ 行，每行两个正整数 $x,y(1\leq x,y\leq 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\leq n\leq 8000,1\leq q\leq 10^6$。
| 子任务编号 | $n\leq$ | $q\leq$ | 特殊性质 | 分值 |
|---|---|---|---|---|
| $1$ | $500$ | $10^6$ | 无 | $10$ |
| $2$ | $2500$ | $20$ | ||
| $3$ | $5000$ | A | $20$ | |
| $4$ | $8000$ | $8000$ | 无 | $20$ |
| $5$ | $8000$ | $10^6$ | $30$ |
特殊性质 A：每条边 $(i,j)(1\leq i < j\leq n)$ 以 $\frac 12$ 概率出现。
时间限制：$3\texttt{s}$
空间限制：$1\texttt{GB}$
提示
请选手相信自己算法的常数与评测机的效率。