你有一个 $$$n \times n$$$ 网格和两个整数 $$$a$$$ 和 $$$b$$$。行和列的编号都是从 $$$1$$$ 到 $$$n$$$。我们将第 $$$i$$$ 行和第 $$$j$$$ 列交叉处的单元格表示为 $$$(i, j)$$$。
您正站在单元格 $$$(1, 1)$$$ 中,并且想要移至单元格 $$$(n, n)$$$。
假设您位于单元格 $$$(i, j)$$$ 中;在一步中,您可以移动到单元格 $$$(i, j + 1)$$$ 或移动到单元格 $$$(i + 1, j)$$$(如果相应的单元格存在)。
让我们将单元格 $$$(i, j)$$$ 的成本定义为 $$$c(i, j) = \gcd(i, a) + \gcd(j, b)$$$ (这里,$$$\gcd(x,y)$$$ 表示 $$$x$$$ 和 $$$y$$$ 的最大公约数)。从 $$$(1, 1)$$$ 到 $$$(n, n)$$$ 的路线成本是访问过的单元格(包括起始单元格和结束单元格)的成本总和。
找到成本可能最小的路线并打印其成本。
输入
唯一的一行包含三个整数 $$$n$$$、$$$a$$$ 和 $$$b$$$ ($$$2 \le n \le 10^6$$$; $$$1 \le a, b \le 10^6$$$)。
输出
打印一个整数 — 从 $$$(1, 1)$$$ 到 $$$(n, n)$$$ 的最便宜路线的成本。
示例
输入 #1
4 2 4
输出 #1
21
输入 #2
10 210 420
输出 #2
125
注意
第一个示例如上图所示。