Варіація НІМа
Варіація НІМа
На столі лежить n купок камінчиків: a_1 камінчиків у першій купці, a_2 камінчиків у другій, ..., a_n в n-ій. Двоє грають у гру, роблячи ходи по черзі. За один хід гравець може або взяти довільну ненульову кількість камінчиків (можливо, усі) з однієї довільної купки, або довільним чином різділити довільну існуючу купку, у якій не менше двох камінчиків, на дві непорожні купки. Програє той, хто не зможе зробитиь хід. Хто виграє при правильній грі?
Вхідні дані
У першому рядку задано ціле число t — кількість тестів (1 ≤ t ≤ 100). Наступні t рядків містять самі тести. Кожен з них починається з цілого числа n — кількості купок (1 ≤ n ≤ 100). Далі йде n цілих чисел a_1, a_2, ..., a_n через пропуск — кількість камінчиків у купках (1 ≤ a_i ≤ 10^9).
Вихідні дані
Виведіть t рядків, у i-ому рядку виведіть "FIRST", якщо у i-ому тесті при правильній грі виграє перший гравець, і "SECOND", якщо другий.
Приклад
3 1 1 2 1 1 3 1 2 3
FIRST SECOND FIRST