题目描述

给定正整数 $p,q$ 以及常数 $N=10^{18}$。现在构建一张包含 $N$ 个结点的带权无向图，结点依次以 $1,2,\ldots,N$ 编号。对于任意满足 $1 \le u<v \le N$ 的 $u,v$，向图中加入一条连接结点 $u$ 与结点 $v$ 的无向边，边权取决于 $u,v$ 是否互质：

• 若 $u,v$ 互质，则边长为 $p$；
• 否则边长为 $q$。

现在给定 $n$ 组询问，每组询问给定两个正整数 $a_i,b_i$，请回答结点 $a_i$ 与结点 $b_i$ 之间的最短距离。

输入格式

第一行输入三个正整数 $n,p,q$，分别表示询问数量、互质边权、不互质边权。

接下来 $n$ 行，每行输入两个正整数 $a_i,b_i$。

输出格式

输出共 $n$ 行，每行一个整数，表示对应最短距离。

4 4 3
1 2
2 3
4 2
3 5

4
4
3
4

数据范围与提示

• 对于 $30$ 的测试点，$1 \le n\le 10$，$1 \le a_i,b_i \le 50$
• 对于另外 $30$ 的测试点，$1 \le a_i,b_i \le 250$
• 对于所有测试点，$1 \le n\le 10^4$，$1 \le a_i,b_i \le 10^9$，$1 \le p,q \le 10^9$

若输入为：

5 2 6 1 2 2 3 4 2 3 5 6 6

输出为：

2 2 4 2 0