Practice on Toph

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

Tom Is a Good Mentor

By Hasinur_ · Limits 1s, 512 MB

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 ≤ 106
1 ≤ N ≤ 106
M = N

Subtask 2: (30 points)
1 ≤ T ≤ 5 × 105
1 ≤ N ≤ 106
1 ≤ M≤ 1018 and M is divisible by N.

Subtask 3: (60 points)
1 ≤ T ≤ 105
1 ≤ N ≤ 106
1 ≤ M ≤ 1018 and M may not be divisible by N.

Input

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.

Output

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

Sample

InputOutput
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

Discussion

Statistics


42% Solution Ratio

quachanhEarliest, 1M ago

DraakKrijgerFCFastest, 0.2s

quachanhLightest, 21 MB

DraakKrijgerFCShortest, 1417B

Submit

Login to submit