{"raw_statement":[{"iden":"statement","content":"一张图有 $n$ 个节点，编号为 $1,2,3,\\dots,n$。其中 $i$ 号节点会向 $j$ 号节点连一条边权为 $|i-j|$ 的无向边，当且仅当 $\\gcd(i,j)=i,\\operatorname{lcm}(i,j)=j$ 时连边。现询问 $q$ 次，每次询问求 $x$ 到 $y$ 的最短路径。"},{"iden":"input","content":"第一行一个 $T$，表示数据组数。\n\n每组数据的第一行两个正整数 $n,q$，表示节点数和询问次数。\n\n接下来 $q$ 行，每行两个正整数 $x,y$，表示起点和终点。"},{"iden":"output","content":"对于每组询问，输出一个正整数。相邻两个输出以换行符隔开。"},{"iden":"note","content":"注意时空限制，本题不捆绑。\n\n对于 $40\\%$ 的数据，$T,n,q\\le100$;\n\n对于 $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$。\n\n**请使用更快的 IO 方式**。\n\nupdata on 2024/8/8：\n\n时限上调到 1000ms。/yun"}],"translated_statement":null,"sample_group":[["1\n6 4\n1 4\n3 5\n2 5\n2 4","3\n6\n5\n2"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}