Tuenti Challenge 9

Challenge 1 - Onion wars

You are celebrating your 20 months anniversary at Tuenti today! As part of the celebration, you have decided to bring some good tortilla española for your coworkers, but you realize that each person only eats tortillas with or without onion.

Given that each person eats half tortilla, what is the minimum number of tortillas you need to ensure that everyone gets their share? Keep in mind that you can only bring whole tortillas, with or without onion.

Note: although it would be correct to bring only tortilla with onion since a tortilla without onion is horrible, we don't want to start an internal war over this, so we want you to bring enough food for both groups.

Input

The first line has an integer C, which is the number of cases for the problem. Then C lines follow and each one has two integers N and M, which are the number of people that want tortillas with and without onion, respectively.

Output

For each case, there should be a line starting with "Case #x: " followed by the minimum number of tortilla you must bring.

Limits

  • 1 ≤ C ≤ 100
  • 0 ≤ N, M ≤ 100000
  • 1 ≤ N + M

Sample Input

3
2 2
3 2
0 1

Sample Output

Case #1: 2
Case #2: 3
Case #3: 1

In the first case, we need one tortilla per group.
In the second case, we need two tortillas (since it is not possible to only bring one and a half) with onions and one without onions.
In the third case, we only need half of a tortilla with onion, but we bring one since they are indivisible.

Problem stats

Completion time: min: 0:01:56 h
10th percentile: 0:10:39 h
90th percentile: 20:01:09 h
max: 104:16:02 h
Test phase time: 10th percentile: 0:08:28 h
90th percentile: 19:05:06 h
Submit phase time: 10th percentile: 0:00:52 h
90th percentile: 0:17:42 h
# of completions:524