TRINO - PUT TRINOMO

no tags 

Given a m × n chess board, determine the minimum number of places to be covered to make it impossible to put a L shaped trinomo on it.

e.g. In 2 × 2 chess board if you cover any 2 cells, it will be impossible to put a L shaped trinomo on it.

1 <= n, m <= 10^8

A trinomo is a L shaped object.

*
* *

where * represents a cell.

Input

T: number of test cases (T <= 5000)

Next T lines:

every line contain m, n

Output

Minimum number of cells to be covered.

Example

Input:
1
2 2

Output:
2

hide comments
nadstratosfer: 2020-04-14 21:58:42

I can't believe I needed almost an hour to get this right. Annoying little problem.

Snehasish Roy ;): 2012-08-05 13:34:26

Totally agree with @aradhya71 Move it to tutorial :D :D :D :D :D :D

BLANKRK: 2012-08-05 10:22:50

nice one!!!

npsabari: 2012-08-04 19:31:12

Got it in 10 seconds!!

Aradhya: 2012-08-04 16:11:30

defntly tutorial..
@devil: there's nthg tricky here. u need jus 1 thing "brain" ;)

:): 2012-08-03 10:06:39

very good and tricky question

Last edit: 2012-08-04 10:01:29
Vaishali Behl: 2012-08-03 06:36:37

please provide some more test cases.


Added by:praveen123
Date:2012-08-02
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:general problem