A13936 | $Division$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

Oleg'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$ . Oleg is really good at division and managed to find all the answers quickly, how about you?

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.

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.

输入 #1

输出 #1

10
4
179

C++ 编辑器

输入

输出