## Chocolate Bar

You have a rectangular chocolate bar. It consists of*m*×

*n*(1≤

*m,n*≤1000) squares. You want to break it up into 1×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×2 bar requires 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×2 pieces, and then use only one more break to achieve your goal.

**Input Format**

The first line contains an integer

*N*, the number of test cases to follow.

Each of the following

*N*lines contains two space-separated integers, the dimensions

*m*and

*n*of a chocolate bar.

**Output Format**

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

**Sample Input**

2

1 2

2 2

**Sample Output**

1

3

All Submissions

Best Solutions

**Point Value:** 5

**Time Limit:** 2.00s

**Memory Limit:** 16M

**Added:** Feb 21, 2009

**Author:** javic

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

H-Shienhon Feb 09, 2016 - 12:48:49 am UTC How do i fix this?jargonon Feb 09, 2016 - 7:31:03 am UTC Re: How do i fix this?H-Shienhon Feb 10, 2016 - 2:10:37 am UTC Re: How do i fix this?example:

-------

1 2(1)prints 1

2 2(2)prints 2

that's how i think the code works, not so sure

jargonon Feb 11, 2016 - 2:51:18 am UTC Re: How do i fix this?In your code, the value of e, which you print, is dependent on previous cases. For example, the following will not work in your code:

Input:

2

2 2

1 2

Output:

3

1

H-Shienhon Feb 11, 2016 - 3:13:45 am UTC Re: How do i fix this?jargonon Feb 11, 2016 - 5:02:49 am UTC Re: How do i fix this?You may gain some insights by reading the previously posted comments.

Also I'm not convinced 100% that you know for sure that the cases are independent... so yeah. They are.

ilovepion Jan 06, 2011 - 2:10:42 am UTC Can anyone help me with the formula?HelloMelloCon Jan 06, 2011 - 11:18:29 pm UTC Re: Can anyone help me with the formula?You just might find a pattern

ilovepion Jan 07, 2011 - 3:40:00 am UTC Re: Re: Can anyone help me with the formula?bbi5291on Jan 07, 2011 - 7:01:40 pm UTC Re: Re: Can anyone help me with the formula?StealthAdepton Feb 21, 2009 - 7:48:21 pm UTC Whybbi5291on Feb 21, 2009 - 7:50:15 pm UTC Re: Whyjavicon Feb 21, 2009 - 5:11:36 am UTC xDbbi5291on Feb 21, 2009 - 2:25:51 pm UTC Re: xDdAedaLon Feb 21, 2009 - 3:24:16 pm UTC Re: xDOverthinking is not fox.

bbi5291on Feb 21, 2009 - 4:36:20 pm UTC Re: Re: xD