### 问题描述 小然在一次冒险中，发现了一个由 $N$ 个顶点组成的无向图。每个顶点都由一个整数标记，从 $1$ 到 $N$。 对于图中的任意两个顶点 $u$ 和 $v$（$u \neq v$），只有当 $u$ 能够整除 $v$ 时，才存在一条从 $u$ 到 $v$ 的无向边，其权重为 $\dfrac{v}{u}$。注意，这样的图不会有自环或多重边。 现在，你需要回答 $Q$ 个查询。在每个查询中，你会得到两个顶点 $u$ 和 $v$，你需要找出从顶点 $u$ 到顶点 $v$ 的最短距离。 ### 输入格式 输入的第一行包含一个整数 $T$，表示测试用例的数量。 每个测试用例包含多行。第一行包含两个整数 $N$ 和 $Q$，分别表示顶点的数量和查询的数量。 接下来 $Q$ 行，每行包含两个整数 $u$ 和 $v$，表示一个查询的两个顶点。 ### 输出格式 对于每个测试用例，输出 $Q$ 行，每行包含一个整数，表示对应查询的最短距离。 ### 样例输入 ```text 1 6 2 3 6 2 3 ``` ### 样例输出 ```text 2 5 ``` ### 说明 在第一个测试用例中，给定 $N = 6$ 和 $2$ 个查询。 在第一个查询中，$u = 3$，$v = 6$。存在一条从 6 到 3 的边，其权重为 2，我们可以沿着这条边前进，所以最短距离为 2。 在第二个查询中，$u = 2$，$v = 3$。存在一条从 2 到 1 的边，其权重为 2，以及一条从 3 到 1 的边，其权重为 3，我们可以先沿着从 2 到 1 的边前进，然后再沿着从 1 到 3 的边前进，所以最短距离为 5。 ### 评测数据范围 $1 \leq T \leq 10^3$。 $2 \leq N \leq 10^5$，$1 \leq Q \leq 10^5$，$1 \leq u, v \leq N$，且 $u \neq v$。 所有测试用例中，$N$ 和 $Q$ 的总和不超过 $10^5$。