给定正整数p,q 以及常数N=10^18 。现在构建一张包含N个结点的带权无向图，结点依次以1,2..,N 编号。对于任意满足1<= u < v <= N 的u,v ，向图中加入一条连接结点u与结点v的无向边，边权取决于u,v是否互质： 若u,v互质（即u,v 的最大公因数为1 ），则连接结点u与结点v的无向边长度为p ； 否则连接结点u与结点v的无向边长度为q。 现在给定n组询问，第i（1<=i<=n ）组询问给定两个正整数ai,bi ，你需要回答结点ai 与结点bi 之间的最短距. 离。 3.1.2 输

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

输出共n行，每行一个整数，表示结点ai与结点bi之间的最短距离

对于30%的测试点，保证1<=n<=10,1<=ai,bi<=50;

对于另外30%的测试点，保证1<=ai,bi<=250;

对于所有测试点,保证1<=n<=10^4,1<=ai,bi<=10^9,1<=p,q<=10^9.