Problem Description

There is a graph with $n$ nodes, numbered $1,2,3,\dots,n$. Node $i$ is connected to node $j$ by an undirected edge with weight $|i-j|$ if and only if $\gcd(i,j)=i$ and $\operatorname{lcm}(i,j)=j$. Now there are $q$ queries. For each query, find the shortest path from $x$ to $y$.

Input Format

The first line contains an integer $T$, meaning the number of test cases.

For each test case, the first line contains two positive integers $n,q$, meaning the number of nodes and the number of queries.

The next $q$ lines each contain two positive integers $x,y$, meaning the start node and the end node.

Output Format

For each query, output one positive integer. Separate adjacent outputs with a newline.

1
6 4
1 4
3 5
2 5
2 4

3
6
5
2

Hint

Pay attention to the time and memory limits. This problem is not bundled.

For $40\%$ of the testdata, $T,n,q\le100$.

For $100\%$ of the testdata, $1\le T\le10^6$, $1\le n,q\le10^6$, $1\le x,y\le n$, and $1\le \sum n,\sum q\le10^6$.

Please use faster I/O methods.

updata on 2024/8/8:

The time limit has been increased to 1000 ms. /yun.

Translated by ChatGPT 5