Sitting (Large)

The opening ceremony of a game world championship is about to start. The players sit in a grid of seats with $R$ rows and $C$ columns.

The competition is fierce, and a player dislikes having future opponents right next to them. A player feels crowded if another player sits in the seat directly to their left and another player sits in the seat directly to their right. A player also feels crowded if one player sits directly in front of them and another player sits directly behind them.

Find the largest number of players that can be seated so that no player feels crowded.

The first line contains the number of test cases $T$. $T$ test cases follow. Each test case is one line with two integers $R$ and $C$: the number of rows and the number of columns of seats.

For each test case, print one line in the form Case #x: y, where $x$ is the test case number starting from 1 and $y$ is the largest number of players that can be seated so that no player feels crowded.

• $1 \le T \le 100$
• $1 \le R \le 100$
• $1 \le C \le 100$

With $R = 2$ and $C = 2$, all four seats can be filled and no player feels crowded.

With $R = 2$ and $C = 3$, a row cannot hold three players, because the middle one would feel crowded. Filling the first two columns seats four players, and nothing better exists.

With $R = 4$ and $C = 1$, filling the first two rows and the last row is optimal and seats three players.