BOMBER - Bomberman

no tags 

Alice and Bob love to play Bomberman. They decided to upgrade the game. Their version is played on a rectangular board divided into cells. The first player puts a bomb on any cell. The bomb destroys this cell, as well as all consecutive undestroyed cells left, right, above and below it. Then the second player puts his bomb, then again the first and so on. The player who destoys the last cell wins the game. Given the dimensions of the board, determine which player wins the game assuming that both players play optimally.

Input

The first line contains T (1 <= T <= 1000) - the number of tests. The next T lines contain two integers m and n (1 <= m, n <= 100) - the size of the board.

Output

For each test print 1 if the first player wins the game, or 2 if the second wins.

Example

Input:
1
2 2

Output:
2

Example of the first two moves of 7x7 board


hide comments
Joaquin: 2016-06-08 02:20:08

Nice problem :)

Francky: 2016-03-17 22:22:43

Image back.

deepika bagaria: 2013-04-13 10:34:56

"all consecutive undestroyed cells left, right, above and below it" mean all undestroyed cells in the given direction until destroyed cell

mAx: 2013-04-13 10:35:00

some more test cases

Spooky: 2013-04-13 10:35:13

all undestroyed cells in the given direction until destroyed cell or end of board is met

ebd: 2013-04-13 10:35:17

"all consecutive undestroyed cells left, right, above and below it" mean all undestroyed cells in the given direction until destroyed cell

Last edit: 2013-03-17 21:36:44
Spooky: 2013-04-13 10:35:22

as usual for this type of problems this means that both players try to win

pavan kumar narreddy: 2013-04-13 10:35:06

"both players play optimally" what is optimal here??
Both try to destroy maximum number of undestroyed cells left at that moment??

Oleg: 2013-04-13 10:34:51

First image.

[Rampage] Blue.Mary: 2013-04-13 10:34:47

Re ":D": +1. For example, if the board is size 5*5 and the bomb is at the middle cell, which image below is right?

UUDUU
UUDUU
DDBDD
UUDUU
UUDUU

or
UUUUU
UUDUU
UDBDU
UUDUU
UUUUU

Last edit: 2010-03-22 04:04:11

Added by:Spooky
Date:2010-03-09
Time limit:0.239s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ADA95 ASM32 ASM64 BASH BF C CSHARP CPP C++ 4.3.2 CPP14 C99 CLPS LISP clisp LISP sbcl D ERL FORTRAN HASK ICON ICK JAVA JS-RHINO LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON RUBY SCALA SCM guile SCM qobi ST TCL WHITESPACE
Resource:Advancement Spring 2010, http://sevolymp.uuuq.com/, author: Alexey Shchepin