3.3 Rohit Loves Division

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?

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

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.

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.

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.

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.