410209: GYM103984 E Division

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?

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 one integer: the greatest number $$$x$$$ that divides $$$p$$$ and is not divisible by $$$q$$$.

10
4

10

12
6

4

179
822

179

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$$$.