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("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
#include <bits/stdc++.h>
 
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
  
using namespace std;
//using namespace __gnu_pbds;
  
void err(istream_iterator<string> it) {cout << '\n';}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
    string s = typeid(a).name();
    cout << "[" << *it << " = ";
    cout << a;
    cout << "] ";
    err(++it, args...);
}
  
#define F first
#define S second
#define ll long long
#define ull unsigned ll
#define pb push_back
#define pf push_front
#define db double
#define ld long double
#define ofk order_of_key
#define fbo find_by_order
#define ppb pop_back
#define ppf pop_front
#define br cout << '\n'
#define pll pair<long long, long long>
#define pipii pair<int, pii>
#define ppiii pair<pii, int>
#define piipii pair<pii, pii>
#define here cout << "HERE\n"
#define bruh cout << "BRUH\n"
#define all(x) (x).begin(),(x).end()
#define sqr(x) (x) * (x)
#define __ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define watch(x) cout << (#x) << " is " << (x) << endl
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define TEST int TT; cin >> TT; for(int T = 1; T <= TT; T++)
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
 
int gcd(int a, int b) {if (a < b) swap(a, b); return b ? gcd(b, a % b) : a;}
ll gcd(ll a, ll b) {if (a < b) swap(a, b); return b ? gcd(b, a % b) : a;}

pair<int, int> dx[] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
  
const int inf = 2e9 + 7;
const ll INF = 9e18 + 7;
//const ld pi = 3.1415926535897932384626433;
const db eps = 1e-6;
//const ld EPS = 1e-9;
int mod = 998244353;
const ll MOD = 1e15 + 7;
 
//mt19937 lol(chrono::steady_clock::now().time_since_epoch().count());
//mt19937_64 rofl(chrono::steady_clock::now().time_since_epoch().count());
 
//random_device random_device;
//mt19937 generator(random_device());
 
const bool multiple_tests = 1;
const int N = 1e6 + 7;
 
#define int long long
#define pii pair<int, int>

int d, k;

bool ok(int x, int y) {
    return (x * x + y * y <= d);
}

void solve() {
    cin >> d >> k; // d < k?
    d *= d;
    bool move = 0;
    int x = 0, y = 0;
    for (;; move ^= 1) {
        if (x == y) x += k;
        else y += k;
        if (!ok(x, y)) break;
    }
    if (move) {
        cout << "Ashish";
    }
    else {
        cout << "Utkarsh";
    }
}



 
/* stuff you should look for
    * int overflow, array bounds
    * special cases (n=1?)
    * do smth instead of nothing and stay organized
    * WRITE STUFF DOWN
    * DON'T GET STUCK ON ONE APPROACH
*/
 
signed main() { __
//  freopen("e.in", "r", stdin);
//  freopen("e.out", "w", stdout);
    int TT = 1;
    if (multiple_tests) cin >> TT;
    for (int testcase = 1; testcase <= TT; testcase++) {
        solve();
        cout << '\n';
    }
     
//    #ifndef SSYernar
//      cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
//    #endif
    return 0;
}
