Chinese Chess

Chinese chess, or Xiangqi is an extremely popular game in the Eastern Hemisphere. It is currently played by millions (or tens of millions) in China's mainland, Taiwan, Thailand, Singapore, Vietnam, Hong Kong and other Asian countries. Chinese chess has remained in its present form for centuries.
The name Chinese chess has an interesting origin. Of China's four traditional arts -- qin (music), qi (strategy games), shu (calligraphy) and hua (brush painting) -- the second term, qi, provides the final syllable of Chinese chess.

Here’s some more information about Chinese chess.

Chinese chess Board



Pieces
Each player has the following pieces:
2 Rooks (R) (or chariots)
2 Knights (N) (or horses)
2 Elephants (M) (or bishops or ministers)
2 Mandarins (G) (or advisors or assistants or guards)
1 King (K) (or generals)
2 Cannons (C)
5 Pawns (P) (or soldiers)



Rules
a) The object of the game is to checkmate or stalemate the opponent. This is accomplished by:
Placing the opponent in check so that he has no legal move to get out of the check.
Stalemating your opponent so that he has no legal move (when you stalemate your opponent, you win--it is not a draw as in chess).
b) Red usually moves first.
c) You cannot check your opponent indefinitely by moving the same piece to the same squares (resulting in perpetual check and a draw in chess). You cannot put the opponent in check more than 3 times in a row with the same piece without either side moving any other piece.
d) Similar to the rule above, you cannot indefinitely "chase" an opposing piece from one square to another if your opponent has no other way to avoid losing the piece. The idea of this rule and the rule above is to avoid perpetual check draws. Some of these situations can be complicated but usually the person who is initiating the perpetual move loop must break it off.
e) The two kings cannot face each other on the same column without any pieces between them.
f) When neither side can capture the opposing king, the game is a draw.


Now your group is developing a Chinese chess software. It’s your task to write a program to check if the moves are legal or not. To simplify this problem, you needn’t to consider the rule b, c, d, f. It means that the result is not important. The only thing you need to do is to judge if the moves are legal. A move is illegal if:
a)  The given coordinates of original and final position are illegal. Such as the position is out of the board, the original position is empty or your opponent’s piece or the final position is your own piece.
b)  The move breaks the move rules and rules above (except rule b, c, d, f)
c)  Something special, if after one move, one of the player’s king has been eaten, if it's the last move, it’s legal, or the next move is illegal. (look at the sample for more details)

  The input consists of several test cases. There is a single number above all, the number of cases. There are no more than 300 cases.
  Each case starts with the initial chess board. There are 10 rows and 9 columns. 0 represents empty point. 1, 2, 3, 4, 5, 6, 7 represent red king, mandarin, elephant, knight, rook, cannon, pawn while 8, 9, 10, 11, 12, 13, 14 represent black pieces. Then two numbers N and K ( ): n is the number of moves and if K=0 red moves first, if K=1 black moves first. Next N lines follow, each containing four integers, representing the coordinates of original position and final position. You may assume that the initial board is always legal. For more details, the board of figure 1 is:
12 11 10 9 8 9 10 11 12
0 0 0 0 0 0 0 0 0
0 13 0 0 0 0 0 13 0
14 0 14 0 14 0 14 0 14
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
7 0 7 0 7 0 7 0 7
0 6 0 0 0 0 0 6 0
0 0 0 0 0 0 0 0 0
5 4 3 2 1 2 3 4 5

If all of the moves are legal, print “Legal move”. If step x is the first illegal move, then print “Illegal move on step x”. If there are several moves are illegal, print the first illegal move only. Use the format in the sample.

3
0 0 0 9 8 0 0 0 0
0 0 0 0 9 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 11 0
0 0 0 0 0 0 0 0 0
0 0 0 0 2 0 0 0 5
0 0 0 2 1 0 0 0 0
3 1
7 8 8 6
9 9 9 6
8 6 10 5
0 0 0 0 8 0 0 0 0
0 0 0 0 7 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 14 1 0 0 0 0
1 0
2 5 1 5
0 0 0 0 8 0 0 0 0
0 0 0 0 7 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 14 1 0 0 0 0
2 0
2 5 1 5
10 4 10 5

Case 1: Illegal move on step 3
Case 2: Legal move
Case 3: Illegal move on step 2

2008 “Sunline Cup” National Invitational Contest