最短距离

题目描述

给定正整数 $p,q$ 以及常数 $N=10^{18}$。现在构建一张包含 $N$ 个结点的带权无向图，结点依次以 $1,2,...,N$ 编号。对于

任意满足 $1\le u<v\le N$ 的 $u,v$，向图中加入一条连接结点 $u$ 与结点 $v$ 的无向边，边权取决于 $u,v$ 是否互质：

若 $u,v$ 互质（即 $u,v$ 的最大公因数为 $1$），则连接结点 $u$ 与结点 $v$ 的无向边长度为 ；

否则连接结点 $u$ 与结点 $v$ 的无向边长度为 $q$。

现在给定 $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

14 4 321 232 344 253 5

输出样例 1

14243344

输入样例 2

15 2 621 232 344 253 566 6

输出样例 2

1222344250

数据范围

对于 $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}$。