Statement : F. Quadratic Jumps
You are given two integers $n$ and $q$. Consider a graph with $n$ vertices, where vertices $i$ and $j$ are connected by an edge if and only if $|j - i|$ is a perfect square$^{\text{∗}}$.
You are given $q$ pairs of numbers $a_i, b_i$. For each of these $q$ pairs, you need to find the shortest distance between vertices $a_i$ and $b_i$ in this graph. It can be proved that the graph is connected, so the distance between $a_i$ and $b_i$ is not infinite.
$^{\text{∗}}$An integer $x$ is a perfect square if there exists an integer $y$ such that $x = y^2$.
Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 1000$). The description of the test cases follows.
The first line of each test case contains two integers $n$ and $q$ ($2 \le n \le 2 \cdot 10^5$, $1 \le q \le 10^5$) — the number of vertices in the graph and the number of pairs of vertices for which the distance must be found.
Then the following $q$ lines describe the pairs of vertices for which the shortest distance must be found. Each pair is described by two numbers $a, b$ ($1 \leq a \lt b \leq n$).
It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$, and the sum of $q$ over all test cases does not exceed $10^5$.
For each test case, output the shortest distance between the vertices for each of the $q$ pairs.
Input
2
5 4
1 2
1 3
1 4
1 5
8 3
3 7
2 5
1 7
Output
1
2
2
1
1
2
3
Note
This is what the graph looks like for the first test case:
- For the first pair of vertices, the shortest path is $1 \rightarrow 2$.
- For the second pair of vertices, the shortest path is $1 \rightarrow 2 \rightarrow 3$.
- For the third pair of vertices, the shortest path is $1 \rightarrow 5 \rightarrow 4$.
- For the fourth pair of vertices, the shortest path is $1 \rightarrow 5$.
This is what the graph looks like for the second test case:
- For the first pair of vertices, the shortest path is $1 \rightarrow 2$.
- For the second pair of vertices, the shortest path is $2 \rightarrow 6 \rightarrow 5$.
- For the third pair of vertices, the shortest path is $1 \rightarrow 2 \rightarrow 6 \rightarrow 7$.