Rogelio has a board of dimensions $$$n \times m$$$, with $$$n \leq 3$$$. The board is very ugly, and he wants to cover it. To cover it, he has three types of pieces:
- Pieces with dimensions $$$1 \times 1$$$, each costing 3 euros.
- Pieces with dimensions $$$1 \times 2$$$, each costing 2 euros.
- Pieces with dimensions $$$1 \times 3$$$, each costing 1 euro.
The pieces can be rotated and flipped in any direction. Rogelio wants to cover the board with the pieces but under the following conditions: the board must be completely covered, there cannot be more than one piece covering the same point on the board, all pieces must be completely within the board, and the total cost must be minimized.
For example, here are three different ways to cover a $$$3 \times 5$$$ board. The one on the right has the minimum possible cost.
The input starts with an integer $$$t$$$ indicating the number of cases.
Each case consists of a line with the integers $$$n$$$ and $$$m$$$.
For each case, write a line with the minimum price that needs to be paid.
$$$1 \leq t \leq 10^4$$$
$$$1 \leq n \leq 3$$$
$$$1 \leq m \leq 10^6$$$
11 Points: $$$1 \leq n,m \leq 3$$$
11 Points: $$$n = 1$$$ and $$$m$$$ is a multiple of $$$3$$$
11 Points: $$$n = 1$$$
11 Points: $$$n = 2$$$ and $$$m$$$ is a multiple of $$$3$$$
11 Points: $$$n = 2$$$
11 Points: $$$n = 3$$$ and $$$m$$$ is a multiple of $$$3$$$
11 Points: $$$n = 3$$$
23 Points: No additional restrictions
3 1 3 2 4 3 5
1 4 5
