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 NN and MM. Jerry has to answer how many integer numbers XX in the range [1,M][1,M] are there so that the condition below will hold for all 1Y<X1 ≤ Y < X and 1Z<N1 ≤ Z < N, where YY and ZZ are positive integers.

X×ZY×NX×Z \neq Y×N

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

Input

First line of the input will contain a single integer TT (1T1061 ≤ T ≤ 10^6). TT denotes the number of test cases. Each of the next TT lines will contain two positive integers NN (1N1061 ≤ N ≤ 10^6) and MM (1M10181 ≤ M ≤ 10^{18}).

Output

For each case print Case t: v\texttt{Case t: v} without quotations where t\texttt{t} is the case number and v\texttt{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

Submit

Login to submit.

Statistics

41% Solution Ratio
quachanhEarliest, Mar '20
mbsabbirr127Fastest, 0.1s
mbsabbirr127Lightest, 5.4 MB
SoudipShortest, 720B
Toph uses cookies. By continuing you agree to our Cookie Policy.