ZUFEOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs ContestProblemSetList
Login Register

问题 A: Haitang and Game

内存限制：256 MB 时间限制：1 S
题面：传统 评测方式：Special Judge 上传者：
提交：10 通过：3
返回比赛提交提交记录

题目描述

Given a set $\textstyle S$, dXqwq and Haitang take turns performing the following operations, with dXqwq going first:

-   Find a pair $\textstyle (x,y)$ such that $\textstyle x,y\in S$ and $\textstyle \gcd(x,y)\notin S$.
    
-   Insert $\textstyle \gcd(x,y)$ into $\textstyle S$.
    

The player who cannot make a move loses the game. You need to output the winner when both players play optimally.

输入格式

Each test contains multiple test cases. The first line contains an integer $\textstyle T$ ($\textstyle 1\leq T\leq 20$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $\textstyle n$ ($\textstyle 1\leq n\leq 10^5$) — the size of set $\textstyle S$.

The second line contains $\textstyle n$ integers $\textstyle a_1,a_2,\cdots,a_n$ ($\textstyle 1\leq a_1<a_2<\cdots<a_n\leq 10^5$) — the elements of set $\textstyle S$.

输出格式

For each test case, output “dXqwq” if dXqwq will win the game, and “Haitang” if Haitang will win the game.

输入样例 复制 

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

输出样例 复制 

Haitang
dXqwq
Haitang
dXqwq
dXqwq

分类标签