BOMBER - Bomberman

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 destroys 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


Added by:Spooky
Date:2010-03-09
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ADA95 ASM32 ASM64 BASH BF C CSHARP C++ 4.3.2 CPP CPP14 C99 CLPS LISP sbcl LISP clisp 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

hide comments
2018-04-15 12:59:35
We destroyed cells untill destroyed cell or end of board is met
2016-06-08 02:20:08 Joaquin
Nice problem :)
2016-03-17 22:22:43 Francky
Image back.
2013-04-13 10:34:56 deepika bagaria
"all consecutive undestroyed cells left, right, above and below it" mean all undestroyed cells in the given direction until destroyed cell
2013-04-13 10:35:00 mAx
some more test cases
2013-04-13 10:35:13 Spooky
all undestroyed cells in the given direction until destroyed cell or end of board is met
2013-04-13 10:35:17 ebd
"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
2013-04-13 10:35:22 Spooky
as usual for this type of problems this means that both players try to win
2013-04-13 10:35:06 pavan kumar narreddy
"both players play optimally" what is optimal here??
Both try to destroy maximum number of undestroyed cells left at that moment??
2013-04-13 10:34:51 Oleg
First image.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.