Optimal Removal Game with GCD

In this problem, two players, Liam and Noah, play a turn-based game on an array of positive integers. On each turn, a player may remove elements provided that the overall greatest common divisor (GCD) of the current array is greater than 1. Both players play optimally. The game ends when a player is unable to make a move. It turns out that the outcome of the game is determined solely by the GCD of the initial array.

Formally, given an array of n integers \(a_1, a_2, \ldots, a_n\), if \(n = 1\) then no move is possible and the result is NOAH. Otherwise, compute the overall GCD \(G = \gcd(a_1, a_2, \ldots, a_n)\). If \(G = 1\) then no valid move exists and the winner is NOAH; if \(G > 1\) then the first player, LIAM, can always force a win.

For example:

• For the array [2, 3, 4], \(\gcd(2, 3, 4) = 1\), so the winner is NOAH.
• For the array [5, 10, 15, 20], \(\gcd(5, 10, 15, 20) = 5 > 1\), so the winner is LIAM.

inputFormat

The input starts with an integer t on its own line, representing the number of games.

Each game is described in two lines: the first line contains an integer n (the number of elements in the array), and the second line contains n space-separated positive integers.

Example:

2
3
2 3 4
4
5 10 15 20

outputFormat

For each game, output a single line containing either LIAM or NOAH, indicating the winner.

Example:

NOAH
LIAM

## sample

2
3
2 3 4
4
5 10 15 20

NOAH
LIAM

</p>