Hide

Problem G
Game of Divisibility

Viet and Nam are playing a game set up with a list of $n$ positive integers $a_1, a_2, \ldots , a_ n$ and a positive integer $k$. Two players alternatively take turns removing a number from the list until the list is empty. The final score of each player is the sum of all numbers removed by that player. The winner of the game is the only player having the score divisible by $k$. It is a draw if the scores of both players are divisible by $k$ or not divisible by $k$.

Your task is to identify the winner of the game assuming that both players play optimally and Viet plays first.

Input

The input consists of several datasets. The first line of the input contains the number of datasets, which is a positive number and is not greater than $50$. Each dataset is described by two lines:

  • The first line contains two positive integers $n$ ($1 \leq n \leq 1\, 024$) and $k$ ($2 \leq k \leq 32$).

  • The second line contains $n$ space-separated integers $a_ i$ ($0 \leq a_ i \leq 2^{31}$).

Output

For each test case, output in one line one word, either FIRST if Viet wins, SECOND if Nam wins or DRAW if the game ends up with a draw.

Sample Input 1 Sample Output 1
3
3 4
4 4 2
3 4
4 4 8
3 4
2 2 2
SECOND
DRAW
FIRST

Please log in to submit a solution to this problem

Log in