给定一个集合 $S$，dXqwq 和 Haitang 轮流进行以下操作，dXqwq 先手：

• 找到一对 $(x, y)$，使得 $x, y \in S$ 且 $\gcd(x, y) \notin S$。
• 将 $\gcd(x, y)$ 插入到 $S$ 中。

无法进行操作的玩家输掉游戏。假设双方均采取最优策略，请输出获胜者的名字。

输入格式

每个测试点包含多个测试用例。第一行包含一个整数 $T$ ($1 \le T \le 20$)，表示测试用例的数量。接下来是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示集合 $S$ 的大小。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_1 < a_2 < \dots < a_n \le 10^5$)，表示集合 $S$ 中的元素。

输出格式

对于每个测试用例，如果 dXqwq 获胜，输出 “dXqwq”；如果 Haitang 获胜，输出 “Haitang”。

样例

输入 1

5
1
24
2
44 77
3
6 10 15
4
11 45 1419 19810
8
2 6 9 10 12 17 18 20

输出 1

Haitang
dXqwq
Haitang
dXqwq
dXqwq