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 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). For each test case, output the shortest distance between each of the (q) pairs of vertices. 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 lik