## MATGAME - Matrix Game

no tags

Two players A and B play the following game.

1) First, a matrix M of size N*M is chosen, and filled with non-zero 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
 < Previous 1 2 Next > Core2Duo: 2010-02-06 14:52:36 Yes. Is the number removed from that number only or from the whole row? Ehor Nechiporenko: 2010-02-03 16:36:33 The player subtracts any number between 1 and K inclusive from it. From what? From number? Last edit: 2010-02-03 16:39:58

 Added by: Varun Jalan Date: 2010-01-25 Time limit: 0.343s 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