# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Today is the first day of the little mouse Jerry at school. Famous mathematician Tom is his teacher. Today, Tom taught Jerry about numbers, powers, etc. After the discussion session, Tom wanted to take a test of Jerry to evaluate how much he learned.

The problem that Tom asked Jerry to solve is simple. Tom will give him two integers **N** and **M**. Jerry has to answer how many integer numbers **X** in the range **[1,M]** are there so that the condition below will hold for all **1 ≤ Y < X** and **1 ≤ Z < N**, where **Y** and **Z** are positive integers.

`$ X×Z \neq Y×N $`

Jerry is clever. So he hired you to write a program to solve the problem for him.

Subtask 1: (10 Points)

1 ≤ T ≤ 10^{6}

1 ≤ N ≤ 10^{6}

M = N

Subtask 2: (30 points)

1 ≤ T ≤ 5 × 10^{5}

1 ≤ N ≤ 10^{6}

1 ≤ M≤ 10^{18}
and M is divisible by N.

Subtask 3: (60 points)

1 ≤ T ≤ 10^{5}

1 ≤ N ≤ 10^{6}

1 ≤ M ≤ 10^{18}
and M may not be divisible by N.

First line of the input will contain a single integer **T**. **T** denotes the number of test cases.
Each of the next **T** lines will contain two positive integers **N** and **M**.

For each case print “Case t: v” without quotations where **t** is the case number and **v** is the required answer.

Input | Output |
---|---|

5 1 1 2 2 3 3 4 4 5 5 | Case 1: 1 Case 2: 1 Case 3: 2 Case 4: 2 Case 5: 4 |

42% Solution Ratio

quachanhEarliest,

DraakKrijgerFCFastest, 0.2s

quachanhLightest, 21 MB

DraakKrijgerFCShortest, 1417B

Login to submit