E. Division
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Oleg's favourite subjects are History and Math, and his favourite branch of mathematics is division. To improve his division skills, Oleg came up with two integers $$$p$$$ and $$$q$$$ and decided to find the greatest number $$$x$$$ that divides $$$p$$$, but is not divisible by $$$q$$$. Oleg is really good at division and managed to find the answer quickly, how about you?

Input

The first line contains an integer $$$p$$$ ($$$1 \le p \le 10^{100}$$$). The second line contains an integer $$$q$$$ ($$$2 \le q \le 10^{12}$$$). One can show that there is always at least one value of $$$x$$$ satisfying the divisibility conditions for the given constraints.

Output

Output one integer: the greatest number $$$x$$$ that divides $$$p$$$ and is not divisible by $$$q$$$.

Examples
Input
10
4
Output
10
Input
12
6
Output
4
Input
179
822
Output
179
Note

In the first example $$$10$$$ is the answer, since it is the maximal divisor of $$$10$$$ and it is not divisible by $$$4$$$.

In the second example $$$12$$$ is not a valid candidate, since $$$12$$$ is divisible by $$$6$$$, and neither is $$$6$$$: it is also divisible by $$$6$$$. The next available divisor is $$$4$$$, which is the answer, since $$$4$$$ is not divisible by $$$6$$$.