最短距离

题目描述

给定正整数 (n) 以及常数 (p, q)。现在构建一张包含 (n) 个结点的带权无向图，结点依次以 (1, 2, \dots, n) 编号。对于任意满足 (1 \le i < j \le n) 的 (i, j)，向图中加入一条连接结点 (i) 与结点 (j) 的无向边，边权取决于 (i, j) 是否互质：若 (i, j) 互质（即最大公因数为 (1)），则边长为 (p)；否则边长为 (q)。

现在给定若干组询问，每组询问给定两个正整数 (a, b)，你需要回答结点 (a) 与结点 (b) 之间的最短距离。

输入格式

第一行，三个正整数 (k, p, q)，分别表示询问数量、结点编号互质时的边权，以及结点编号不互质时的边权。 接下来 (k) 行，每行两个正整数 (a, b)，表示一组询问。

输出格式

输出共 (k) 行，每行一个整数，表示结点 (a) 与结点 (b) 之间的最短距离。

样例

输入样例 1

4 4 3
1 2
2 3
4 2
3 5

输出样例 1

4
4
3
4

数据范围

对于所有测试点，保证 (1 \le k \le 10^5)，(1 \le p, q \le 10^9)，(1 \le a, b \le 10^9)。

注：原始 PDF 因字体原因丢失了数据范围里的数字，此处重建为 (1 \le k \le 10^5)，(1 \le p, q \le 10^9)，(1 \le a, b \le 10^9)。