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$$$.

Input

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 next $$$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$$$) — the numbers of the vertices between which the shortest distance must be found.

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$$$.

Output

For each test case, output the shortest distance between each of the $$$q$$$ pairs of vertices.

Note

This is what the graph looks like for the first test case:

$\text{[math]}$

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:

$\text{[math]}$

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$$$.

Idx	Name	Rating
A	Construct an Array	800
B	Another Sorting Problem	1100
C	Chipmunk Theo and Equality	1400
D	Maximum Prefix Sums	1900
E	Graph Cutting	2300
F	Quadratic Jumps	2600

Codeforces Round 1099 (Div. 2)