410209: GYM103984 E Division

Memory Limit:512 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

E. Divisiontime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard 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$$$.

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

加入题单

上一题 下一题 算法标签: