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>
#include<bits/stdc++.h>
using namespace std;

#define     fRead           freopen("INPUT.txt","r",stdin)
#define     fWrite          freopen("OUTPUT.txt","w",stdout)
#define     ss(a)           scanf("%s",a)
#define     gs(s)           getline(cin,s)
#define     gc              getchar()
#define     si(a)           scanf("%d",&a)
#define     sii(a,b)        scanf("%d%d",&a,&b)
#define     siii(a,b,c)     scanf("%d%d%d",&a,&b,&c)
#define     sl(a)           scanf("%lld",&a)
#define     sll(a,b)        scanf("%lld%lld",&a,&b)
#define     slll(a,b,c)     scanf("%lld%lld%lld",&a,&b,&c)
#define     sd(a)           scanf("%lf",&a)
#define     sdd(a,b)        scanf("%lf%lf",&a,&b)
#define     sddd(a,b,c)     scanf("%lf%lf%lf",&a,&b,&c)
#define     deb(x)          cout << #x " = " <<(x) << endl
#define     debb            printf("####\n")
#define     pi(a)           printf("%d",a)
#define     ps(a)           cout<<a
#define     pl(a)           printf("%lld",a)
#define     pd(a)           printf("%f",a)
#define     pc(a)           printf("%c",a)
#define     bl              printf("\n")
#define     pf              printf
#define     spc             printf(" ")
#define     ll              long long
#define     llu             unsigned long long
#define     pie             (2*acos(0.0))
#define     eps             1e-9
#define     qi              queue<int>
#define     vi              vector<int>
#define     vs              vector<string>
#define     vd              vector<double>
#define     vl              vector<long long>
#define     pb              push_back
#define     all(a)          a.begin(),a.end()
#define     rall(a)         a.rbegin(),a.rend()
#define     pii             pair <int,int>
#define     pll             pair <ll,ll>
#define     mem(a,b)        memset(a,b,sizeof(a))
#define     fl(i,a,n)       for(int i=a; i<n; i++)
#define     rfl(i,n,a)      for(int i=n-1; i>=a; i--)
#define     fit(x,mp)       for(auto x = mp.begin(); x!=mp.end(); x++)
#define     MAX             100000 //10^5
#define     inf             1000000000 //10^9
#define     mod             1000000007 //10^9

int t, cs;
ll d, k;
pll get(int i, int x, int y)
{
    if(i%2==0) x += k;
    else y += k;
    return make_pair(x,y);
}
ll sqr(ll x)
{
    return x*x;
}
int main()
{
    si(t);
    while(t--)
    {
        cin>>d>>k;
        ll p, q;
        p = q = 0;
        int idx = -1;
        string ans = "Ashish";
        while(1)
        {
            idx++;
            pll P = get(idx, p, q);
            p = P.first;
            q = P.second;
            if( (sqr(p)+sqr(q)) > sqr(d))
            {
                //deb(ans);
                if(idx%2==0) ans = "Utkarsh";
                break;
            }
        }
        //deb(idx);
        ps(ans);bl;
    }
    return 0;
}




