Boring Question
Tag(s):

## Easy, Number Theory

Problem
Editorial
Analytics

Please forgive us, we could'nt come up with any story.Just solve this Boring Question to get 100 points :).

There is a N X M array of switches controlling N X M matrix of bulbs .

Initially, all the bulbs are in OFF state, You just have to turn all the bulbs ON, but there is a defect in the switch system.

If any one of the switches is toggled(OFF to ON and vice versa) all the switches of adjacent bulbs also gets toggled(including the bulbs which are diagonal to it) thereby turning them ON/OFF also

So, it becomes an easy task now, tell us the number of minimum toggles required to turn all the bulbs ON.

Input :

First Line of each test case tells the total number of cases T. The next T lines gives the value of N X M

Output:

Print the minimum number of toggels required to turn all the lights ON. Changing line after every Case.

Constraints:

1 <= T <= 1000000

0<= N <= 10^9

0<= M <= 10^9

SAMPLE INPUT
6
1 1
1 2
2 1
4 1
2 2
3 3
SAMPLE OUTPUT
1
1
1
2
1
1
Explanation

All the cases are Obvious except the 4th. For the 4th you will require minimum 2 toggles to turn all the bulbs ON. (solution is to toggle the first and the last bulb).

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

Beginner Practice Round 1.0

OTHER PROBLEMS OF THIS CHALLENGE
• Basic Programming > Bit Manipulation
• Basic Programming > Implementation
• Math > Basic Math
• Basic Programming > Implementation
• Algorithms > Sorting