Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

math

number theory

*1500

No tag edit access

The problem statement has recently been changed. View the changes.

×
C. Division

time limit per test

1 secondmemory limit per test

512 megabytesinput

standard inputoutput

standard outputOleg's favorite subjects are History and Math, and his favorite branch of mathematics is division.

To improve his division skills, Oleg came up with $$$t$$$ pairs of integers $$$p_i$$$ and $$$q_i$$$ and for each pair decided to find the greatest integer $$$x_i$$$, such that:

- $$$p_i$$$ is divisible by $$$x_i$$$;
- $$$x_i$$$ is not divisible by $$$q_i$$$.

Input

The first line contains an integer $$$t$$$ ($$$1 \le t \le 50$$$) — the number of pairs.

Each of the following $$$t$$$ lines contains two integers $$$p_i$$$ and $$$q_i$$$ ($$$1 \le p_i \le 10^{18}$$$; $$$2 \le q_i \le 10^{9}$$$) — the $$$i$$$-th pair of integers.

Output

Print $$$t$$$ integers: the $$$i$$$-th integer is the largest $$$x_i$$$ such that $$$p_i$$$ is divisible by $$$x_i$$$, but $$$x_i$$$ is not divisible by $$$q_i$$$.

One can show that there is always at least one value of $$$x_i$$$ satisfying the divisibility conditions for the given constraints.

Example

Input

3 10 4 12 6 179 822

Output

10 4 179

Note

For the first pair, where $$$p_1 = 10$$$ and $$$q_1 = 4$$$, the answer is $$$x_1 = 10$$$, since it is the greatest divisor of $$$10$$$ and $$$10$$$ is not divisible by $$$4$$$.

For the second pair, where $$$p_2 = 12$$$ and $$$q_2 = 6$$$, note that

- $$$12$$$ is not a valid $$$x_2$$$, since $$$12$$$ is divisible by $$$q_2 = 6$$$;
- $$$6$$$ is not valid $$$x_2$$$ as well: $$$6$$$ is also divisible by $$$q_2 = 6$$$.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/24/2024 00:39:41 (j3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|