(RankList for this Question)
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?
Constraints
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
Input:
3
10 4
12 6
179 822
Output:
10
4
179
Explanation:
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