RAYGUN - Ray Gun

You are in an m x n grid. You are standing in position (0, 0) and in each of the other lattice points (points with integer co-ordinates) an enemy is waiting. Now you have a ray gun that can fire up to infinity and no obstacle can stop it. Your target is to kill all the enemies. You have to find the minimum number of times you have to fire to kill all of them. For a 4 x 4 grid you have to fire 13 times. See the picture below:

Input

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

Each case contains two integers m, n (0 ≤ m, n ≤ 109) and at least one of them will be less than or equal to 106.

Output

For each case, print the case number and the minimum number of times you have to fire to kill all the enemies.

Sample Input

Output for Sample Input

2

4 4

10 10

Case 1: 13

Case 2: 65

 


Added by:Race with time
Date:2012-11-06
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.