题目描述

一张图有 $n$ 个节点，编号为 $1,2,3,\dots,n$。其中 $i$ 号节点会向 $j$ 号节点连一条边权为 $|i-j|$ 的无向边，当且仅当 $\gcd(i,j)=i,\operatorname{lcm}(i,j)=j$ 时连边。现询问 $q$ 次，每次询问求 $x$ 到 $y$ 的最短路径。

输入格式

第一行一个 $T$，表示数据组数。

每组数据的第一行两个正整数 $n,q$，表示节点数和询问次数。

接下来 $q$ 行，每行两个正整数 $x,y$，表示起点和终点。

输出格式

对于每组询问，输出一个正整数。相邻两个输出以换行符隔开。

1
6 4
1 4
3 5
2 5
2 4

3
6
5
2

提示

注意时空限制，本题不捆绑。

对于 $40\%$ 的数据，$T,n,q\le100$;

对于 $100\%$ 的数据，$1\le T\le10^6$，$1\le n,q\le10^6$，$1\le x,y\le n$，$1\le \sum n,\sum q\le10^6$。

请使用更快的 IO 方式。

updata on 2024/1/6：

时限从 500ms 略微上调至 750ms。