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.