Background

Holmes and Watson are playing a game, but Holmes always wins.

When will Watson realize that the initial positions generated by Holmes always have a guaranteed winning strategy?

Problem Description

Holmes and Watson are playing a math-related game.

Initially, there are $n$ integers $a_1\sim a_n$ on the table.
They take turns to act. On a player's turn, they must choose one of the following two operations to perform:

• Choose a number $a_i$ on the table and divide it by its largest prime factor.
• Choose a number $a_i$ on the table and change it to its own square. At any time, the total number of times this player uses this operation cannot exceed their total score.

After a player finishes an operation, if there is a number equal to $1$ on the table, remove it and let this player gain $1$ point.
Both players start with score $0$. If there are no numbers left on the table, the game ends, and the player with the higher score wins.
Holmes moves first. Assuming both players use optimal strategies, determine who will win, or output a draw.

Input Format

This problem contains multiple test cases.
The first line contains an integer $T$, the number of test cases.
For each test case:
The first line contains an integer $n$, the number of integers on the table.
The second line contains $n$ integers $a_1\sim a_n$, representing the $n$ integers on the table.

Output Format

Output $T$ lines. Each line contains a string: if the game ends in a draw, output Draw. Otherwise, if Holmes can win, output Lucky_Holmes. Otherwise output Angry_Waston.

3
1
2
2
2 2
1
4

Lucky_Holmes
Draw
Angry_Waston

4
3
9 10 15
3
9 10 30
2
11 14
4
11 4 5 14

Angry_Waston
Lucky_Holmes
Lucky_Holmes
Angry_Waston

3
8
7 12 15 17 21 23 30 31
10
10 11 12 13 14 15 16 17 18 19
6
16 17 18 16 17 18

Angry_Waston
Angry_Waston
Angry_Waston

Hint

Explanation for Sample 1:

There are 3 test cases in total.

In the first test case, there is a single $2$. Holmes can perform operation 1 once to turn $2$ into $1$. Watson cannot make any move. Therefore, Holmes wins.

In the second test case, there are two $2$'s. No matter how Holmes plays, he can only eliminate one $2$ and get 1 point; Watson can always get 1 point as well, so the result is a draw.

In the third test case, there is only one $4$. After Holmes performs operation 1, Watson moves and scores, so Watson wins.

Explanation for Sample 2

In the first test case, $9 = 3\times 3, 10 = 2\times 5, 15 = 3\times 5$. No matter which number Holmes chooses to operate on, Watson can then perform an operation and score, so Watson wins.

For all testdata, $1\le T\le10^4$, $1\le\sum{n}\le2\times10^6$, $2\le a_i\le10^7$.

Translated by ChatGPT 5