CF1444A Division

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.

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 $ . The next available divisor of $ p_2 = 12 $ is $ 4 $ , which is the answer, since $ 4 $ is not divisible by $ 6 $ .