TopCoder

User's AC Ratio

75.0% (3/4)

Submission's AC Ratio

66.7% (6/9)

Description

數字拼盤是個很古老的遊戲,由Sam Loyd在1870年左右所發明,盤面由一個九宮格構成,上面有八個可移動的方塊,分別是編號1到8,遊戲的目的是要藉由移動這八個方塊,使盤面回到最初的狀態也就是八個方塊依照數字排序,而方塊只能往空格的地方移動。


以上圖為例,這個盤面可移動的方塊有兩種選擇,分別是2 (可往下移動)以及3 (可往右移動)。而盤面終止的條件為數字1在左上角、數字2在正上方、數字3在右上角、數字4在最左邊、數字5在中間、數字6在最右邊、數字7在左下角、數字8在正下方、而空格在右下方,如下圖:

小達達的媽媽送了他一個數字拼盤,但正如名字一般,小達達的頭腦阿達阿達的,他把拼盤打亂後根本不知道要如何把拼盤弄回來,有一天他帶著數字拼盤到學校的時候,恰好被班上成績最好的同學小君君看到,小君君看著他的數字拼盤說:”這麼簡單的遊戲,我20步以內就能解出來了”。小達達聽了很不甘心,他決定要找出無法20步之內解出來的狀態。

Input Format

輸入檔中會有多筆資料,第一行是一個正整數k,代表一共有多少組資料,接下來是k組測試資料,每組測試資料有三行,每行三個用空白隔開的數字代表數字拼盤的盤面狀態,其中0代表空格的位置。

Output Format

對每組測試資料,如果這組測試資料能夠在20步以內被解出來,請輸出Easy,其餘的狀況請輸出Hard。

Sample Input

2
1 2 3
4 5 6
8 7 0
1 2 3
4 5 6
7 0 8

Sample Output

Hard
Easy

Hints

Problem Source

原TIOJ1492 / NPSC2007決賽(prob H)

Subtasks

For Testdata: 0 ~ 0, Score: 100
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 10000 65536 262144