수학적인 최소 공통 조상

문제

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

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

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

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

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

입력

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

출력

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

힌트

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

예제 입력 1 복사

1 4

예제 입력 2 복사

21 49

예제 입력 3 복사

30 20

예제 출력 1 복사

1

예제 출력 2 복사

7

예제 출력 3 복사

5