Problem K
Split It!
Carol is preparing a Split It tournament. Split It is a turn-based line-drawing game, played by two players on a piece of paper. On each turn a player draws a horizontal or vertical line segment that starts at a point with integer coordinates on an existing line segment and ends at another point with integer coordinates on an existing line segment, and does not intersect any line segment at any point other than those endpoints. Players alternate taking turns. A player loses the game if after drawing a line segment they create a $1\times 1$ box enclosed on all sides by line segments.
The initial state for an $m$-by-$n$ Split It game has 4 line segments already drawn, namely, $(0,0)$ to $(m,0)$, $(m,0)$ to $(m,n)$, $(m,n)$ to $(0,n)$, and $(0,n)$ to $(0,0)$.
The night before the tournament, Carol printed out the game sheets for the tournament participants, where each game sheet has an initial state of $4$ line segments as described above. It is now the day of the tournament, but oh no! Disaster! Upon checking the printed game sheets, Carol has found that each of the games has been sabotaged! In addition to the 4 line segments making up the usual initial state, each game has a fifth horizontal or vertical line segment already drawn in, beginning at one of the edges, but not necessarily extending all the way to the opposite edge.
It is too late now to re-print the Split It game sheets. Carol wants to assess how this will affect the tournament. Given the lengths of the initial line segments, and a description of the fifth line segment already drawn in, determine whether Player 1 or Player 2 will win if Player 1 goes first and both players play optimally.
Input
The first line consists of a single integer, $G$, the number of game sheets, where $1\leq G\leq 50$. This is followed by $G$ lines, each consisting of $5$ space-separated integers, $m, n, x, y, k$. The integers $m,n$ give the side lengths of an unsabotaged game, where $2\leq m,n\leq 20$. The integers $x,y$ give the position of one endpoint of the fifth line segment drawn in, and $k$ is the length of that line segment. That is, $(x,y)$ are coordinates such that $x=0$ or $x=m$ or $y=0$ or $y=n$, and $0\leq x\leq m$ and $0\leq y \leq n$, and $k$ is the length of the line segment extending from $(x, y)$ perpendicular to the line segment that $(x,y)$ lies on, towards the opposite line segment. If $x=0$ or $x=m$, then $1\leq k\leq m$ and $1\leq y \leq n-1$. If $y=0$ or $y=n$, then $1\leq k \leq n$ and $1\leq x \leq m-1$.
Output
For each of the $G$ games, output one line containing the integer $1$ if Player 1 will win with optimal play, otherwise the integer $2$ if Player 2 will win with optimal play.
| Sample Input 1 | Sample Output 1 |
|---|---|
2 5 3 1 0 2 3 4 3 2 1 |
2 1 |
