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
2013-04-13 10:34:47 [Rampage] Blue.Mary
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
2013-04-13 10:34:42 :D
I'm not sure if I understand this correctly. The bomb destroys the whole lines of undestroyed cell in all four directions, right?
2013-04-13 10:34:38 Spooky
the bomb should be placed on the undestroyed cell
2013-04-13 10:35:46 .:: Pratik ::.
"The first player puts a bomb on any cell. "
Or is it, any "undestroyed cell". Is it not possible to run an infinite game if you can place on a destroyed cell. ?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.