← 返回题目列表

Codeforces · 1451/D

D. 圆圈游戏

中文机器翻译题面 查看原题

Utkarsh 被迫玩 Ashish 的另一款游戏。游戏轮流进行,和往常一样,阿什什先行动。

考虑 2D 平面。有一个令牌最初位于 $$$(0,0)$$$。在一次移动中,玩家必须将标记的 $$$x$$$ 坐标或 $$$y$$$ 坐标恰好增加 $$$k$$$。这样做时,玩家必须确保令牌与 $$$(0,0)$$$ 保持在(欧几里德)距离 $$$d$$$ 内。

换句话说,如果移动后标记的坐标为 $$$(p,q)$$$,则 $$$p^2 + q^2 \leq d^2$$$ 必须成立。

当玩家无法移动时游戏结束。可以证明,游戏将以有限步数结束。如果两名玩家都发挥最佳,则确定谁会获胜。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 100$$$) — 测试用例的数量。

每个测试用例的唯一行包含两个空格分隔的整数 $$$d$$$ ($$$1 \leq d \leq 10^5$$$) 和 $$$k$$$ ($$$1 \leq k \leq d$$$)。

输出

对于每个测试用例,如果 Ashish 赢得了比赛,则打印“Ashish”,否则打印“Utkarsh”(不带引号)。

示例

输入 #1

5
2 1
5 2
10 3
25 4
15441 33

输出 #1

Utkarsh
Ashish
Utkarsh
Utkarsh
Ashish

注意

在第一个测试用例中,一个可能的移动序列可以是

$$$(0, 0) \xrightarrow{\text{阿什什 }} (0, 1) \xrightarrow{\text{乌特卡什 }} (0, 2)$$$。

Ashish 没有剩余步数,因此 Utkarsh 获胜。