Chocolate Bar

View as PDF

Submit solution

All submissions

Best submissions

Points: 5

Time limit: 1.0s

Memory limit: 16M

Problem type

You have a rectangular chocolate bar. It consists of $m \times n$ $m \times n$ $(1 \le m,n \le 1\,000)$ $(1 \leq m, n \leq 1 000)$ squares. You want to break it up into $1 \times 1$ $1 \times 1$ pieces (individual squares). What is the minimum number of times that you must break the chocolate bar, or pieces thereof, in order to achieve this? Note that you cannot stack pieces of the bar and break them, because the chocolate bar is thick. As an example, a $2 \times 2$ $2 \times 2$ bar requires $3$ $3$ breaks. First you can break it in half, then break each of the halves in half. You cannot break it in half, stack the two $1 \times 2$ $1 \times 2$ pieces, and then use only one more break to achieve your goal.

Input Specification

The first line contains an integer $N$ $N$ , the number of test cases to follow.
Each of the following $N$ $N$ lines contains two space-separated integers, the dimensions $m$ $m$ and $n$ $n$ of a chocolate bar.

Output Specification

A line containing a single integer for each case given in the input: the answer for the corresponding case.

Sample Input

Copy

2
1 2
2 2

Sample Output

Copy

1
3

Comments

0

Ri_Si_Zz commented on Oct. 8, 2024, 7:50 p.m.

wanna eat chocolate orz