3.3 Rohit Loves Division
(RankList for this Question)
Score: 50pts
Time Limit: 5.00 sec
Rohit loves Geography and Math, and his favourite topic in Maths is division.
To further improve his division, Rohit made t pairs of integers a and b and for each pair decided to find the greatest integer y such that:
- a is divisible by y
- y is not divisible by b
Rohit is an expert in division and was able to find all the answers instantly, how about you?

1 ≤ t ≤ 50
1 ≤ a ≤ 10^18
2 ≤ b ≤ 10^9

Input Format
The first line contains an integer t (1 ≤ t ≤ 50) — the number of pairs.

Each of the following t lines contains two integers a and b (1 ≤ a ≤ 10^18, 2 ≤ b ≤ 10^9) — the pair of integers given.

Output Format
For each test case, print the value of y.

One can prove that there is always at least one value of y satisfying the divisibility conditions for the given constraints.

Example 1
10 4
12 6
179 822


For the first pair, where a=10 and b=4, the answer is y=10, since it is the greatest divisor of 10 and 10 is not divisible by 4.

For the second pair, where a=12 and b=6, note that
- 12 is not a valid y, since 12 is divisible by b=6;
- 6 is not valid y as well, since 6 is also divisible by b=6.
The next available divisor of a=12 is 4, which is the answer, since 4 is not divisible by 6.

Log In to solve the Question