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

• 若 u,v 互质（即 u,v 的最大公因数为 1），则连接结点 u 与结点 v 的无向边长度为 p；
• 否则连接结点 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 之间的最短距离。

说明/提示

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