H. Mr. Benzene's Bachelor Trip
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Mr. Benzene wants permission to go on a bachelor trip, but his mathematician wife isn't convinced.

She says:

Solve this math problem first — or you're cleaning the room all week!"

Mr. Benzene must find the smallest non-negative integer $$$\mathbf{n}$$$ such that the number of ways to express $$$\mathbf{n}$$$ as the sum of exactly $$$\mathbf{k}$$$ non-negative integers is at least $$$\mathbf{m}$$$. If he fails, he faces a week of messy floors and dust bunnies.

Input

The first line contains an integer $$$\textbf{T}$$$ $$$(1 \leq $$$T$$$ \leq 10^{5})$$$ the number of test cases.

Each of the next $$$T$$$ lines contains two integers $$$\textbf{k}$$$ and $$$\textbf{m}$$$ $$$(1 \leq $$$k$$$ ,\, $$$m$$$ \leq 10^{18})$$$.

Output

For each test case, output Case $$$\mathbf{X: n}$$$, where $$$\mathbf{X}$$$ is the test case number (starting from 1) and $$$\mathbf{n}$$$ is the smallest integer that satisfies the condition, or $$$\mathbf{-1}$$$ if no such answer exists.

Example
Input
3
3 15
3 16
5 35
Output
Case 1: 4
Case 2: 5
Case 3: 3
Note

Consider the first test case: $$$\mathbf{k = 3}, \mathbf{m = 15}$$$. Iterative approach:

  • For $$$n = 0$$$: Ways = $$$(0,0,0)$$$ $$$\to$$$ 1 way. Total ways = 1 $$$ \lt 15$$$.
  • For $$$n = 1$$$: Ways = $$$(0,0,1), (0,1,0), (1,0,0)$$$ $$$\to$$$ 3 ways. Total ways = 3 $$$ \lt 15$$$.
  • For $$$n = 2$$$: Ways = $$$(0,0,2),\, (0,1,1),\, (0,2,0),\, (1,0,1),\, (1,1,0),\, (2,0,0)$$$ $$$\to$$$ 6 ways. Total ways = 6 $$$ \lt 15$$$.
  • For $$$n = 3$$$: Ways = $$$(0,0,3),\, (0,1,2),\, (0,2,1),\, (0,3,0),\, (1,0,2),\, (1,1,1),\, (1,2,0),\, (2,0,1), \\ (2,1,0), (3,0,0)$$$ $$$\to$$$ 10 ways. Total ways = 10 $$$ \lt 15$$$.
  • For $$$n = 4$$$: Ways = $$$(0,0,4),\, (0,1,3),\, (0,2,2),\, (0,3,1),\, (0,4,0),\, (1,0,3),\, (1,1,2),\, (1,2,1), \\ (1,3,0),\, (2,0,2),\, (2,1,1),\, (2,2,0),\, (3,0,1),\, (3,1,0),\, (4,0,0)$$$ $$$\to$$$ 15 ways. Total ways = 15 $$$\ge 15$$$ (Condition met!).

So, the answer is $$$\mathbf{4}$$$.