Let's Solve a Geometry Problem

Interview

Time limit2sMemory limit512 MB

Summary

Given a fraction p/q, find the smallest base b >= 2 in which p/q has a finite (terminating) expansion.

Level: Medium6 of 10
Topics: Number theory, Math, Implementation, Sorting
Solved: No attempts yet

Problem

A is solving a geometry problem again today. When solving geometry problems, it is important to be careful of floating-point errors.

A floating-point error is an error caused by rounding that occurs when a number is represented as a finite binary fraction. For example, $0.1$ in decimal is the infinite binary fraction $0.00011001100110011 ...$ , and rounding this to a finite number of digits produces an error.

Positive integers $p$ and $q$ are given in decimal. Find a base $b$ ( $b$ is an integer greater than or equal to 2) in which the rational number $p$ / $q$ can be represented as a finite decimal. If there are multiple such bases, output the smallest one.

Input

The input is given from standard input in the following format.

$p$ $q$

Output

Output the answer on one line.

Constraints

$0 < p < q < 10^9$

Examples2

Example 1
Input
```
1 2
```
Expected output
```
2
```
Example 2
Input
```
21 30
```
Expected output
```
10
```