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>
//#pragma GCC optimize("O")
#include <bits/stdc++.h>
using namespace std;
template<typename F,typename S,typename T>struct Triple{F first;S second;T third;Triple(F a,S b,T c){first=a,second=b,third=c;}Triple(){first=F(0),second=S(0),third=T(0);}};
template<typename F,typename S,typename T>bool operator<(const Triple<F,S,T>&a,const Triple<F,S,T>&b){return(a.first<b.first?true:(a.first==b.first?(a.second<b.second?true:(a.second==b.second?a.third<b.third:false)):false));}
template<typename F,typename S,typename T>ostream&operator<<(ostream&os,const Triple<F,S,T>&a){os<<a.first<<' '<<a.second<<' '<<a.third;return os;}
template<typename Fi,typename Se,typename Th,typename Fo>struct Quad{Fi first;Se second;Th third;Fo fourth;Quad(Fi a,Se b,Th c,Fo d){first=a,second=b,third=c,fourth=d;}Quad(){first=Fi(0),second=Se(0),third=Th(0),fourth=Fo(0);}};
template<typename Fi,typename Se,typename Th,typename Fo>bool operator<(const Quad<Fi,Se,Th,Fo>&a,const Quad<Fi,Se,Th,Fo>&b){return(a.first<b.first?true:(a.first==b.first?(a.second<b.second?true:(a.second==b.second?(a.third<b.third?true:(a.third==b.third?a.fourth<b.fourth:false)):false)):false));}
template<typename Fi,typename Se,typename Th,typename Fo>ostream&operator<<(ostream&os,const Quad<Fi,Se,Th,Fo>&a){os<<a.first<<' '<<a.second<<' '<<a.third<<' '<<a.fourth;return os;}
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define int ll
#define double ld
typedef pair<int,int>pii;
typedef pair<double,double>pdd;
typedef Triple<int,int,int>ti;
typedef Triple<double,double,double>td;
typedef Quad<int,int,int,int>qi;
typedef vector<int>vi;
typedef vector<vi>vvi;
#define LONG_INF (ll(3e18))
#define INT_INF ((1<<30)-int32_t(1e7))
#define ui unsigned int
#define fi(f,t) for(int i=f;i<int(t);++i)
#define fj(f,t) for(int j=f;j<int(t);++j)
#define fk(f,t) for(int k=f;k<int(t);++k)
#define fq(n) for(int q=0;q<int(n);++q)
#define fs(s) for(auto&shift:s)
#define within_bounds(x,y,a,b) (x>-1&&y>-1&&x<a&&y<b)
#define CLEAR "\x1B[2J\x1B[H"
const int MOD=1e9+7;
const int PRECISION=6;
const double EPS = 1e-6;
const vector<pii>SHIFTS={{0,1},{-1,0},{0,-1},{1,0}};
const vector<pii>KING_SHIFTS={{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1},{1,0},{1,1}};
const vector<pii>KNIGHT_SHIFTS={{-1,2},{-2,1},{-2,-1},{-1,-2},{1,-2},{2,-1},{2,1},{1,2}};
const auto boostIO=[](){ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);cout<<fixed<<setprecision(PRECISION);return 0;}();
inline double logn(const double&n,const double&base){return log(n)/log(base);}
inline int mod(const int&a,const int&b=MOD){int r=a%b;return(r<0?r+b:r);}
inline int pown(int n,int power,const int modulo=MOD){int res=1;while(power){if(power&1)res=mod(res*n,modulo);n=mod(n*n,modulo);power>>=1;}return res;}
inline int min(const pii&p){return(p.first<p.second?p.first:p.second);}


int32_t main()
{

  int t;cin>>t;
  fq(t) {
    double d,k;cin>>d>>k;
    int wow = (d / k) / sqrt(2);
    int x = ((-k*k)+k*sqrt(2*d*d-k*k))/(2*k*k);
    if (wow < x + 1)
      cout << "Ashish\n";
    else
      cout << "Utkarsh\n";
  }

  cout.flush();
  getchar();
  return 0;
}


