MATGAME  Matrix Game
Two players A and B play the following game.
1) First, a matrix M of size N*M is chosen, and filled with nonzero numbers.
2) Player A starts the game and the players play alternately.
3) In his turn, a player chooses any row which has atleast one non zero nuumber in it. In this row, the leftmost non zero number is chosen. Let this number be K. The player subtracts any number between 1 and K inclusive from it.
4) The game ends when all the numbers in the matrix M are 0.
5) The player who plays last wins the game.
Given N,M and the initial matrix, determine who wins the game. Assume that both players play optimally.
Input
The first line contains the number of test cases T.
Each test case consists of 2 numbers N and M. There follow N lines each having M integers. The jth number on the ith line is the number M[i][j]. There is a blank line between consecutive test cases.
Output
Output T lines, one for each case. Output "FIRST" if player A wins, else output "SECOND".
Example
Sample Input :
3
2 2
1 1
1 1
1 3
2 1 1
2 2
3 2
3 2
Sample Output:
SECOND
FIRST
SECOND
Constraints
T <= 1000
1 <= N,M <= 50
The initial matrix values are between 1 and 50 inclusive.
hide comments
tusharjape:
20180611 10:05:20
Has anyone done this without using Sprague Grundy number? I would like to know an alternative approach. 

sxie12:
20170625 23:01:39
@luv_misra Second should win


luv_misra:
20170604 18:08:02
1


Md. Najim Ahmed:
20160319 09:16:53
i dont know much game theory but man... i had fun solving it :v and that even in one attempt ...


jkelava6:
20150629 13:21:27
: : still coding _ :: first player will take 2 in his first move. THEN they both take one. First player wins! 

: : still coding _ ::
20150309 08:54:49
in second test case if each player substracts 1 in his/her turn each time...the answer will be second..? 

Utkarsh Saxena:
20141230 12:10:33
uff!!.. my first game theory question.. nice :D 

Deepak gupta:
20140417 02:08:58
great problem :) 

Shwetank sharad:
20130713 19:01:16
someone please post some more test cases 

Varun Jalan:
20100207 07:24:35
just that number..not the whole row 
Added by:  Varun Jalan 
Date:  20100125 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: NODEJS OBJC PERL6 SQLITE VB.NET 
Resource:  own problem used for Codechef Snackdown 