Generator Synchronization Cycle

Source: Phước Hưng OJ

Version: Phuoc Hung OJ Extended

Problem Statement

Two generators have positive integer periods $n$ and $m$. They start together at time $0$. The first generator returns to its start at times $n,2n,3n,\ldots$ and the second at $m,2m,3m,\ldots$. Find the first positive integer time $k$ when both return simultaneously. Time $0$ is excluded.

Input

One line contains two positive integers $n$ and $m$, the two periods, in this order.

Output

Print the smallest positive integer $k$ divisible by both $n$ and $m$.

Subtasks

• Subtask 1 (20%): $1\le n,m\le20$.
• Subtask 2 (30%): $1\le n,m\le1000$.
• Subtask 3 (50%): $1\le n,m\le10^4$.

Examples

Example 1

Input:

4 6

Output:

12

Explanation: The first returns at 4, 8, 12, ...; the second at 6, 12, 18, ... . Their first common positive time is 12.

Example 2

Input:

7 7

Output:

7

Explanation: The periods are both 7. Their first simultaneous positive return is at time 7.

Example 3

Input:

1 10000

Output:

10000

Explanation: A period-1 generator returns at every positive integer time. The other first returns at 10000, which is therefore their first common positive time.