數字遊戲


提交程序


分数: 100 (部分)
时间限制: 6.0s
内存限制: 64M

作者:
题目类型

小愛和天衣是好朋友,她們玩一個遊戲:
一開始有一個正整數 \(n\),她們輪流做以下三種操作之一,約定小愛是先手。

  1. 將 \(n\) 改為 \(n+1\)
  2. 將 \(n\) 改為 \(n-1\)
  3. 將 \(n\) 除以 \(n\) 最小的質因數

先將正整數換成 \(1\) 者勝,問誰有必勝策略。


Input

第一行包含一個整數\(T\),代表有幾筆測資。
每筆測試資料中包含一行一個整數 \(n > 1\),代表一開始的正整數。

Output

對於每筆測試資料,輸出一行:
如果小愛必勝,輸出 Ai
如果天衣必勝,輸出 Ai
如果沒有人有必勝策略,輸出 Draw

Constraints

第 \(1\) 組測資有 \(n\leq10\),\(T\leq10\)。

第 \(2\) 組測資有 \(n\leq100\),\(T\leq100\)。

第 \(3\) 組測資有 \(n\leq10^9\),\(T\leq100\)。

第 \(4\) 組測資有 \(n\leq10^6\),\(T\leq10^6\)。

第 \(5\) 組測資有 \(n\leq10^9\),\(T\leq10^6\)。

Sample Input
5
3
4
8
9
81
Sample Output
Ai
Ai
Ai
Draw
Draw
Hint

範例測試說明如下:

\(n=3\) 時,小愛直接做操作 3 就獲勝,小愛勝。

\(n=4\) 時,小愛做三種操作分別會使 \(n=5,3,2\),無論哪種天衣做操作 3 就獲勝了,天衣勝。

\(n=8\) 時,小愛選擇操作 3 會使 \(n=4\),無論天衣選哪種操作都會陷入像上面一樣的困境,小愛勝。

\(n=9\) 時,小愛不會選操作 2 或 3 ,否則分別有 \(n=8,3\),前者由上知天衣選操作 3 會勝利,後者天衣選操作 3 直接勝。因此,小愛會選操作 2 讓 \(n=10\)。
同樣的,天衣如果選操作 1 或 3 也會導致小愛的勝利,所以她會選操作 2 使 \(n=9\) 回到前面的情況,因此沒有人會勝利。

\(n=81\) 略。


评论

目前没有评论。