Sitting (Small)

A puzzle game tournament is in full swing. Many players have gathered in an auditorium to fight for the world championship. At the opening ceremony, the players sit in a grid of seats with $R$ rows and $C$ columns.

The competition is fierce, and the players are sensitive about sitting near too many of their future opponents. A player feels too crowded if another player sits directly to their left and another player sits directly to their right. A player also feels too crowded if one player sits directly in front of them and another player sits directly behind them.

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

The first line contains the number of test cases $T$. $T$ test cases follow. Each test case consists of one line with two integers $R$ and $C$, separated by a space: the number of rows and the number of columns of chairs in the auditorium.

For each test case, print one line containing Case #x: y, where $x$ is the test case number starting from 1 and $y$ is the maximum number of players that can be seated.

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

In the first case of the sample, every seat can be filled and no player feels too crowded.

In the second case, each row has three seats. Three players cannot share one row, because the middle player would feel too crowded. Filling each of the first two columns seats four players, which is optimal.

In the third case, filling the first two rows and the last row seats three players, which is optimal.