隨機性無處不在，貫穿著人生的始終。即便是在至關重要的比賽中，決定勝負的關鍵往往也可能只是運氣。

在 2035 年，有 $n$ 位《皇室戰爭》遊戲的狂熱愛好者想要比較誰的水平更高。為了公平起見，他們決定兩兩對戰，總共進行了 $\frac{n(n-1)}{2}$ 場比賽。

然而，彼時的《皇室戰爭》已經徹底演變為「石頭剪刀布」！因此，每一場比賽中，雙方獲勝的機率均為 $50\%$，且相互獨立。

輸了的玩家自然心有不甘。為了獲得「精神勝利」，他們引入了「間接戰勝」的概念：定義 $u$ 是 $k$-間接戰勝 $v$，當且僅當存在 $k$ 個人 $a_1, \dots, a_k$ 使得 $u$ 戰勝了 $a_1$，$a_1$ 戰勝了 $a_2$，$a_i$ 戰勝了 $a_{i+1}$ ($\forall i \in [1, k)$)，$a_k$ 戰勝了 $v$。

特別地，若 $u$ 直接戰勝了 $v$，那麼稱為 0-間接戰勝。

玩家們因此產生了新的疑問：在給定兩名玩家 $u$ 和 $v$ 的情況下，最小需要經過多少層間接關係，才能說 $u$ 戰勝了 $v$？

換句話說，你需要求出最小的整數 $k$，使得 $u$ 可以 $k$-間接戰勝 $v$。因為心有不甘的玩家特別多，你需要回答 $q$ 個詢問。

輸入格式

請注意：本題的 IO 量較大，建議使用較快的讀入和輸出方式，例如：C++ 中使用 scanf printf 或者關閉流同步的 cin cout。建議避免使用一些讀入輸出較慢的語言。

第一行兩個整數 $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$ 行，第 $i$ 行兩個整數 $u_i, v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$) 表示第 $i$ 個詢問。

輸出格式

輸出 $q$ 行，第 $i$ 行一個整數 $k$ 表示最小的 $k$ 使得 $u_i$ 是 $k$-間接戰勝了 $v_i$。特別地，如果對於任何的 $k$，$u_i$ 都無法 $k$-間接戰勝 $v_i$，那麼輸出 -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