最短距离

题目描述

给定正整数 以及常数 。现在构建⼀张包含 个结点的带权⽆向图，结点依次以 编号。对于 任意满⾜ 的 ，向图中加⼊⼀条连接结点 与结点 的⽆向边，边权取决于 是否互质： 若 互质（即 的最⼤公因数为 ），则连接结点 与结点 的⽆向边长度为 ； 否则连接结点 与结点 的⽆向边长度为 。 现在给定 组询问，第 （ ）组询问给定两个正整数 ，你需要回答结点 与结点 之间的最短距 离。

输入格式

第⼀⾏，三个正整数 ，分别表⽰询问数量，结点编号互质时的边权，以及结点编号不互质时的边权。 接下来 ⾏，每⾏两个正整数 ，表⽰⼀组询问。

输出格式

输出共 ⾏，每⾏⼀个整数，表⽰结点 与结点 之间的最短距离。

样例输入 #1

4 4 3
1 2
2 3
4 2
3 5

样例输出 #1

4
4
3
4

样例输入 #2

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

样例输出 #2

2
2
4
2
0

数据范围

对于 % 的测试点，保证 ， 。 对于另外 % 的测试点，保证 。 对于所有测试点，保证 ， ， 。

知识点与难度

本题涉及的知识点从属于 GESP 8级，难度等级：⭐⭐⭐⭐⭐⭐⭐ 。

测试点分布

生测试数据后，按实际 subtask 分组改写上表。