时间限制：1000 ms
内存限制：512 MiB
标准输入输出
题目类型：传统
评测方式：文本比较
给定正整数 以及常数 。现在构建一张包含 个结点的带权无向图，结点依次以 编号。对于任意满足 的 ，向图中加入一条连接结点 与结点 的无向边，边权取决于 是否互质：
- 若 互质（即 的最大公因数为 ），则连接结点 与结点 的无向边长度为 ；
- 否则连接结点 与结点 的无向边长度为 。
现在给定 组询问，第 （）组询问给定两个正整数 ，你需要回答结点 与结点 之间的最短距离。
第一行，三个正整数 ，分别表示询问数量，结点编号互质时的边权，以及结点编号不互质时的边权。
接下来 行，每行两个正整数 ，表示一组询问。
输出共 行，每行一个整数，表示结点 与结点 之间的最短距离。
样例输入 1
样例输出 1
样例输入 2
5 2 6
1 2
2 3
4 2
3 5
6 6
样例输出 2
对于 的测试点，保证 ，。
对于另外 的测试点，保证 。
对于所有测试点，保证 ，，。