26092번 - 수학적인 최소 공통 조상

문제

10ドル^{12}$ 개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1ドル$번부터 10ドル^{12}$번까지 번호가 매겨져 있고 1ドル$번 정점은 루트이다.

이 트리는 다음과 같은 특수한 성질을 가지고 있다.

• 2ドル$ 이상 $N$ 이하의 정수 $x$에 대해 $x$의 가장 작은 소인수를 $p$라고 하자.
• $x$번 정점의 부모 정점은 $\frac{x}{p}$번 정점이다.

두 정점의 가장 가까운 공통 조상은, 두 정점을 모두 자손으로 가지면서 깊이가 가장 깊은 정점으로 정의한다.

두 정수 $a$와 $b$가 주어졌을 때, $a$번 정점과 $b$번 정점의 가장 가까운 공통 조상의 번호를 구해보자.

입력

첫째 줄에 정수 $a$와 $b$가 공백으로 구분되어 주어진다. $(1\leq a,b\leq 10^{12})$

출력

첫째 줄에 $a$번 정점과 $b$번 정점의 가장 가까운 공통 조상의 번호를 출력한다.

제한

노트

어떤 정점의 자손은 자기 자신을 포함한다.