You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

请注意本题的特殊时间限制。

题目描述

走出了幻想乡的路线后，烤乐滋非常开心，他想在草坪上玩耍，烤乐滋望见了前方的草坪，但是草坪在数字王国里，想要进入数字王国，就必须要解决门前的 $q$ 个谜题，这 $q$ 个谜题是这样的：因数个数大于等于 $3$ 的数字为幻想数，你需要求出 $l \sim r$ 中非幻想数的总数与幻想数的总数的大小关系。若幻想数字总数大于非幻想数字总数，则输出 AWada!，否则输出 AKTang!。

不保证 $l \le r$，如果 $l > r$，请你输出 AKTang。

输入格式

第一行一个正整数 $q$，

之后 $q$ 行每行两个正整数 $l,r$。

输出格式

对于每个询问，你需要回答一个字符串并换行。

输入输出样例 #1

输入 #1

10
114 514
233 2333
191 9810
99 999999
3487 6120
6 7
998244353 998244354
1000000007 1000000007
16 17
3 5

输出 #1

AWada!
AWada!
AWada!
AWada!
AWada!
AKTang!
AKTang!
AKTang!
AKTang!
AKTang!

说明/提示

对于 $20\%$ 的数据，满足 $1 \le l,r \le 10^2$，

对于 $50\%$ 的数据，满足 $1 \le l,r \le 10^6$，

对于满足 $1 \le l,r \le 10^6$ 的 $10\%$ 的数据保证 $l,r$ 均匀随机生成。

对于 $10\%$ 的数据，满足 $l=1,r=10^{9}$。

对于 $100\%$ 的数据，满足 $1 \le q \le 10^6$，$1 \le l,r \le 10^{9}$。

对于有 $r > 10^6$ 的数据，保证 $q \le 10^5$。