ランダム性は至る所に存在し、人生の始まりから終わりまでを貫いています。極めて重要な試合においてさえ、勝敗を決める鍵が単なる運であることは珍しくありません。

2035年、 $n$ 人の『クラッシュ・ロワイヤル』の熱狂的なファンが、誰のレベルがより高いかを比較したいと考えました。公平を期すため、彼らは総当たり戦を行うことにし、合計で $\frac{n(n-1)}{2}$ 試合が行われました。

しかし、当時の『クラッシュ・ロワイヤル』は完全に「じゃんけん」と化していました！そのため、各試合において双方が勝利する確率はどちらも 50% であり、かつ互いに独立です。

敗北したプレイヤーは当然納得がいきません。「精神的勝利」を得るために、彼らは「間接勝利」という概念を導入しました。 $u$ が $v$ に対して $k$-間接勝利するとは、ある $k$ 人のプレイヤー $a_1, \dots, a_k$ が存在し、$u$ が $a_1$ に勝利し、$a_1$ が $a_2$ に勝利し、$a_i$ が $a_{i+1}$ に勝利し ($i \in [1, k)$)、$a_k$ が $v$ に勝利することを指します。 特に、$u$ が $v$ に直接勝利した場合、0-間接勝利と呼びます。

プレイヤーたちは新たな疑問を抱きました。2人のプレイヤー $u$ と $v$ が与えられたとき、$u$ が $v$ に勝利したと言えるまで、最小で何層の間接関係を経る必要があるでしょうか？

言い換えれば、$u$ が $v$ に対して $k$-間接勝利できるような最小の整数 $k$ を求める必要があります。納得のいかないプレイヤーが非常に多いため、$q$ 個のクエリに答える必要があります。

入力

注意：本問題の入出力量は大きいため、高速な入出力方式（C++であれば scanf/printf や、同期をオフにした cin/cout など）の使用を推奨します。入出力が遅い言語の使用は避けることを推奨します。

1行目に2つの整数 $n, q$ ($2 \le n \le 5000, 1 \le q \le 10^5$) が与えられます。

続く $n-1$ 行のうち、$i$ 行目は長さ $n-i$ の 01 文字列です。そのうち $j$ 番目 ($1 \le j \le n-i$) の数字が 1 であれば $i$ 番目の人が $i+j$ 番目の人に勝利したことを表し、そうでなければ $i+j$ 番目の人が $i$ 番目の人に勝利したことを表します。勝敗関係は独立にランダム生成され、確率はそれぞれ 50% であることが保証されます。

続く $q$ 行には、各クエリとして2つの整数 $u_i, v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$) が与えられます。

出力

$q$ 行出力してください。$i$ 行目には、$u_i$ が $v_i$ に対して $k$-間接勝利できるような最小の $k$ を出力してください。特に、どのような $k$ に対しても $u_i$ が $v_i$ に対して $k$-間接勝利できない場合は -1 を出力してください。

入出力例

入力 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

出力 1

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

入力 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

出力 2

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