题目描述

有一张包含 $n$ 个点的无向图，点编号为 $1$ 到 $n$。

若 $|i-j|$ 是一个完全平方数，则点 $i$ 与点 $j$ 之间有一条边。

给定 $q$ 个询问 $(a,b)$，请回答从 $a$ 到 $b$ 的最短路长度。保证图是连通的。

输入格式

每个测试包含多组测试数据。

第一行包含整数 $t$（$1 \le t \le 1000$）。

每组测试数据第一行包含两个整数 $n,q$（$2 \le n \le 2\cdot 10^5$，$1 \le q \le 10^5$），分别表示图的点数和询问数。

接下来 $q$ 行，每行包含两个整数 $a,b$（$1 \le a < b \le n$），表示一个询问。

保证所有测试数据的 $n$ 之和不超过 $2\cdot 10^5$，$q$ 之和不超过 $10^5$。

输出格式

对于每组测试数据，按询问顺序输出每对点之间的最短路长度。

样例 1

2
5 4
1 2
1 3
1 4
1 5
8 3
3 7
2 5
1 7

1
2
2
1
1
2
3

约束与提示

• 时间限制：2 秒

• 内存限制：256 MB

• 原题编号：CF2231F