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 p^2 + q^2 ≤ d^2 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 ≤ t ≤ 100) — the number of test cases.

The only line of each test case contains two space separated integers d (1 ≤ d ≤ 10^5) and k (1 ≤ k ≤ 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) \xrightarrow{Ashish } (0, 1) \xrightarrow{Utkarsh } (0, 2).

Ashish has no moves left, so Utkarsh wins.

<image>
/*/ Author: Aniruddh Lawande /*/
#include<bits/stdc++.h>
using namespace std;

/*/---------------------------Defines----------------------/*/
 
#define ll long long
#define F first
#define S second
#define pb push_back
#define endl "\n"
#define all(v) (v).begin(),(v).end()

typedef pair<ll,ll> pii;
/*/-----------------------Modular Arithmetic---------------/*/
 
const long long INF = 1ll << 32; 
const int mod=1e9+7;
inline int add(int x,int y){
    x+=y;
    if (x>=mod) return x-mod;
    return x;
}
inline int sub(int x,int y){
    x-=y;
    if (x<0) return x+mod;
    return x;
}
inline int mul(int x,int y){
    return (x*1ll*y)%mod;
}
inline int power(int x,int y){
    int ans=1;
    while(y){
        if (y&1) ans=mul(ans,x);
        x=mul(x,x);
        y>>=1;
    }
    return ans;
}
inline int inv(int x){
    return power(x,mod-2);
}

const ll FACTORIAL_SIZE = 1.1e6;
ll fact[FACTORIAL_SIZE], ifact[FACTORIAL_SIZE];
void gen_factorial(ll n) {
	fact[0] = fact[1] = ifact[0] = ifact[1] = 1;
		
	for (ll i = 2; i <= n; i++) {
		fact[i] = (i * fact[i - 1]) % mod;
	}
	ifact[n] = inv(fact[n]);
	for (ll i = n - 1; i >= 2; i--) {
		ifact[i] = ((i + 1) * ifact[i + 1]) % mod;
	}
}


ll nck(ll n, ll k) {
	ll den = (ifact[k] * ifact[n - k]) % mod;
	return (den * fact[n]) % mod;
}

/*/-----------------------------Code begins----------------------------------/*/
const int N=2e5+5;

void solve()
{
    ll d,k;
    cin>>d>>k;
    ll x=0,y=0;
    ll i=0;
    while(x*x+y*y<=d*d)
    {
        if(i%2==0)
        {
            if((x+k)*(x+k)+y*y<=d*d) x+=k;
            else break;
        }
        else
        {
            if(x*x+(y+k)*(y+k)<=d*d) y+=k;
            else break;
        }
        i++;
    }
    if(i%2!=0)
    {
        cout<<"Ashish"<<endl;
    }
    else
    {
        cout<<"Utkarsh"<<endl;
    }
    
}



int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
	int tc=1;
	cin>>tc;
    int i=1;
	while(tc--)
	{
        //cout<<"CASE #"<<i<<": ";
		solve();
        i++;
	}
	return 0;
}

