You are placed into a N×M horrible grid at S. This grid is called a horrible grid because it is full of harmful insects and they always ready to bite you. But as you are placed in this grid, you have to leave this grid at any cost. So you want to leave this grid in an optimal way such that you have to take as minimum steps as possible. In one step , you can go any of 8 direction such that from a square you can go to left, right, up, down, left-up corner, left-down corner, right-up corner, right-down corner square. Now, you are given the number of row (N) and number of column (M) of horrible grid. You have to output the minimum steps that require leaving this grid. Remember that, you have only one way (E) to leave this grid.

A 4×5 Horrible Grid

Input

Input starts with an integer T (≤ 100), denoting the number of test cases.

Each case contains two integers N and M (1 ≤ N, M ≤ 10⁹).

Output

For each test case, print the case number and minimum steps required to leave this grid.

Example

Input:
3
4 5
9 10
15 16

Output:
Case 1: 4
Case 2: 9
Case 3: 15

Problem Setter: Md Abdul Alim, Dept. of Computer Science, Bangladesh University of Business & Technology