该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定一张包含 $n$ 个节点的无向图，每个点的编号为$1,2,3...n$，若两个点 $x,y$ 满足 $\gcd(x,y)=x,\operatorname{lcm}(x,y)=y$时，x和y之间就有一条边权为$|x-y|$的无向边。现询问 $q$ 次，每次询问求 $f$ 到 $t$ 的最短路径。

输入格式

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

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

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

输出格式

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

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 f,t\le n$，$1\le \sum n,\sum q\le10^6$。

请使用更快的 IO 方式。