测试数据来自 system/2025

描述

欧拉函数 \(\phi(n)\) 统计了 \(1\) 到 \(n\) 中与 \(n\) 互素的数字个数，例如 \(\phi(9)=6\)。

现在给定正整数 \(A\) 和 \(B\)，请找出最小的正整数 \(n\) 满足 \(\frac{\phi(n)}{n-1} < \frac{A}{B}\)。

格式

输入格式

输入只有一行，是两个正整数 \(A\) 和 \(B\)，满足 \(1\le A<B\le 10^6\)。

输出格式

输出一个正整数，表示最小满足条件的 \(n\)。

样例1

样例输入1

1 2

样例输出1

6

样例2

样例输入2

2 5

样例输出2

12

限制

对于 \(20\%\) 的数据，保证答案不超过 \(10^7\)。

对于 \(30\%\) 的数据，保证答案不超过 \(2.5\times 10^{8}\)。

对于 \(40\%\) 的数据，保证答案不超过 \(7\times 10^{9}\)。

对于 \(50\%\) 的数据，保证答案不超过 \(2.5\times 10^{11}\)。

对于 \(60\%\) 的数据，保证答案不超过 \(3.5\times 10^{14}\)。

对于 \(70\%\) 的数据，保证答案不超过 \(1.5\times 10^{16}\)。

对于 \(80\%\) 的数据，保证答案不超过 \(7\times 10^{17}\)。

对于 \(90\%\) 的数据，保证答案不超过 \(3.5\times 10^{30}\)。

对于 \(100\%\) 的数据，保证答案不超过 \(10^{200}\)。

每一组数据的时限为 \(1\) 秒。