Oleg's cherished subjects are History and Math, and his beloved part of science is division. To further develop his division abilities, Oleg thought of t sets of integers pi and qi and for each pair chose to track down the best integer xi, to such an extent that:
Correct answer will be upvoted else Multiple Downvoted. Don't submit random answer. Computer science.
Oleg's cherished subjects are History and Math, and his beloved part of science is division.
To further develop his division abilities, Oleg thought of t sets of integers pi and qi and for each pair chose to track down the best integer xi, to such an extent that:
pi is detachable by xi;
xi isn't detachable by qi.
Oleg is great at division and figured out how to find every one of the appropriate responses rapidly, you should?
Input
The primary line contains an integer t (1≤t≤50) — the number of sets.
Every one of the accompanying t lines contains two integers pi and qi (1≤pi≤1018; 2≤qi≤109) — the I-th pair of integers.
Output
Print t integers: the I-th integer is the biggest xi with the end goal that pi is detachable by xi, yet xi isn't distinct by qi.
One can show that there is consistently somewhere around one worth of xi fulfilling the distinctness conditions for the given imperatives
Step by step
Solved in 4 steps with 1 images
