Circle Game（博弈论）

链接

Utkarsh is forced to play yet another one of Ashish’s games. The game progresses turn by turn and as usual, Ashish moves first.

Consider the 2D plane. There is a token which is initially at (0,0). In one move a player must increase either the x coordinate or the y coordinate of the token by exactly k. In doing so, the player must ensure that the token stays within a (Euclidean) distance d from (0,0).

In other words, if after a move the coordinates of the token are (p,q), then p2+q2≤d2 must hold.

The game ends when a player is unable to make a move. It can be shown that the game will end in a finite number of moves. If both players play optimally, determine who will win.

Input

The first line contains a single integer $t(1\le t\le 100)$ — the number of test cases.

The only line of each test case contains two space separated integers $d(1\le d\le 105)$ and $k(1\le k\le d)$.

Output

For each test case, if Ashish wins the game, print “Ashish”, otherwise print “Utkarsh” (without the quotes).

Example

input

5
2 1
5 2
10 3
25 4
15441 33

output

Utkarsh
Ashish
Utkarsh
Utkarsh
Ashish

Note

In the first test case, one possible sequence of moves can be

$(0,0)\to Ashish(0,1)\to Utkarsh(0,2)$.

Ashish has no moves left, so Utkarsh wins.

思路

找到一个 $(xk,xk)$ 点，使得 $(xk,xk)$ 在圆内，$(xk+1,xk+k)$ 在圆外。

1. 若 $(xk,xk+k)$ 在圆外，那么先手必败。

因为 $(xk,xk+1)$ 在圆外，所以 $(xk+1,xk)$ 也在圆外。也即是说， $(xk,xk)$ 先手必败。那么 $(xk-k,xk)$ 与 $(xk,xk-k)$ 先手必胜，$(xk-k,xk-k)$先手必败。从而，所有横纵坐标相同的点先手必败。

2. 否则先手必胜。

首先，可以通过不等式证明：当 $(xk,xk)$ 在圆内，$(xk+k,xk+k)$ 在圆外时，$(xk+2k,xk)$ 与 $(xk,xk+2k)$ 必在圆外。当 $(xk+k,xk)$ 也在圆内时，对于这个点，他向上或向右都超出了圆外，所以 $(xk+k,xk)$ 是必败状态。同理，$(xk,xk+k)$ 也先手必败，那么 $(xk,xk)$ 先手必胜。从而，所有横纵坐标相同的点都先手必胜。

#include
#define int long long
using namespace std;
int T,d,k;void solve(){cin>>d>>k;int x=sqrt(d*d/2);x-=x%k;if(x*x+(x+k)*(x+k)>d*d) cout<<"Utkarsh\n";else cout<<"Ashish\n";
}signed main(){ios::sync_with_stdio(false);for(cin>>T;T;T--) solve();
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！