题目描述 给定正整数 $p,q$ 以及常数 $N=10^{18}$。 现在构建一张包含 $N$ 个结点的带权无向图，结点依次以 $1,2,…,N$ 编号。 对于任意满足 $1 \le u < v \le N$ 的 $u,v$，向图中加入一条连接结点 $u$ 与结点 $v$ 的无向边，边权取决于 $u,v$ 是否互质： 现在给定 $n$ 组询问，第 $i$（$1 \le i \le n$）组询问给定两个正整数 $a i,b i$，你需要回答结点 $a i$ 与结点 $b i$ 之间的最短距离。 输入格式 第一行，三个正整数 $n,p,q$，分别表示询问数量，结点编号互质时的边权，以及结点编号不互质时的边权。 接下来 $n$ 行，每行两个正整数 $a i,b i$，表示一组询问。 输出格式 输出共 $n$ 行，每行一个整数，表示结点 $a i$ 与结点 $b i$ 之间的最短距离。 数据范围 $1 \le n \le 10^4$, $1 \le a i,b i \le 10^9$, $1 \le p,q \le 10^9$ 输入样例1 4 4 3 1 2 2 3 4 2 3 5 输出样例1 4 4 3 4 输入样例2 5 2 6 1 2 2 3 4 2 3 5 6 6 输出样例2 2 2 4 2 0