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>
//#include <ext/pb_ds/assoc_container.hpp> 
//#include <ext/pb_ds/tree_policy.hpp> 
 
//using namespace __gnu_pbds;
using namespace std;
 
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define lb lower_bound
#define ub upper_bound
#define ff first
#define ss second
#define null 0
#define pi 3.14159265358979323846
#define all(x) x.begin(), x.end()
#define d0(x) cout<<x<<" ";
#define d1(x) cout<<x<<"\n";
#define d2(x,y) cout<<x<<" "<<y<<"\n";
#define d3(x,y,z) cout<<x<<" "<<y<<" "<<z<<"\n";
#define d4(x,y,z,w) cout<<x<<" "<<y<<" "<<z<<" "<<w<<"\n";

//template<class T> using oset =tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update> ;
 
template<typename T, typename U> static inline void amin(T &x, U y){if (y < x)x = y;} 
template<typename T, typename U> static inline void amax(T &x, U y){if (y > x)x = y;} 
 
typedef long long int ll;
typedef unsigned long long int ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
const long long inf = (ll)1e18+17;
const int inff = 1500000000;
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
const  ll mod= 1000000007;

bool test_case=1;
void solve(){
    ll d,k;
    cin>>d>>k;
    ll x=0,y=0;
    while(1){
        x+=k;
        if(x*x+y*y>d*d){
            cout<<"Utkarsh\n";return;
        }
        y+=k;
        if(x*x+y*y>d*d){
            cout<<"Ashish\n";return;
        }
    }    
}

int main()
{  
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int t=1;
    if(test_case==1) cin>>t;
    //pre();
    for(int i=1;i<=t;i++){
       //cout<<"Case #"<<i<<": ";
       solve();
    }
    return 0;
}
 
// ============== Notes =============== //
// - remove ios_base for interactive problems
// - int overflow (especially intermediate expressionns)
// - array bounds 
// - special cases (n=1? graph not connected?)
