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;
const long double EPS = 10e-9;
const int INF = 1e9 + 5;
const long long INFLL = (long long)INF * (long long)INF;
const long long MOD = 1e9 + 7;
const long double PI = 3.14159265358979323846;
struct HASH {
  size_t operator()(const pair<int, int> &x) const {
    return hash<long long>()(((long long)x.first) ^
                             (((long long)x.second) << 32));
  }
};
void __print(int x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(long long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }
template <typename T, typename V>
void __print(const pair<T, V> &x) {
  cerr << '{';
  __print(x.first);
  cerr << ',';
  __print(x.second);
  cerr << '}';
}
template <typename T>
void __print(const T &x) {
  int f = 0;
  cerr << '[';
  for (auto &i : x) cerr << (f++ ? "," : ""), __print(i);
  cerr << "]";
}
void _print() { cerr << "\n"; }
template <typename T, typename... V>
void _print(T t, V... v) {
  __print(t);
  if (sizeof...(v)) cerr << ", ";
  _print(v...);
}
struct Offset {
  set<long long> s;
  long long delta;
  long long getMinimum() { return (*s.begin()) + delta; }
  long long getMaximum() { return (*s.rbegin()) + delta; }
  void increase(long long x) { delta += x; }
  void add(long long x) { s.insert(x - delta); }
  void remove(long long x) { s.erase(x - delta); }
  bool contains(long long x) { return s.count(x - delta) != 0; }
};
long long rand(long long a, long long b) { return a + rand() % (b - a + 1); }
long long f(long long x, long long y) { return x * x + y * y; }
void solve() {
  long long d, k;
  cin >> d >> k;
  if (k * k > d) {
    cout << "Utkarsh"
         << "\n";
    return;
  }
  long long y = k * (d / k);
  long long x = 0;
  vector<pair<int, int>> pts;
  while (y >= 0) {
    while (f(x + k, y) <= d * d) {
      x += k;
    }
    pts.emplace_back(x, y);
    y -= k;
  }
  vector<pair<int, int>> v;
  for (int i = 1; i < pts.size() - 1; i++) {
    v.push_back(pts[i]);
  }
  if (v.empty()) {
    cout << "Ashish"
         << "\n";
    return;
  }
  if (v.size() % 2) {
    pair<int, int> p = v[v.size() / 2];
    int cnt = (p.first + p.second) / k;
    if (cnt % 2) {
      cout << "Ashish"
           << "\n";
    } else {
      cout << "Utkarsh"
           << "\n";
    }
  } else {
    pair<int, int> p1 = v[v.size() / 2];
    pair<int, int> p2 = v[v.size() / 2 - 1 >= 0 ? v.size() / 2 - 1 : 0];
    int cnt1 = (p1.first + p1.second) / k;
    int cnt2 = (p2.first + p2.second) / k;
    if ((cnt1 % 2) || (cnt2 % 2)) {
      cout << "Ashish"
           << "\n";
    } else {
      cout << "Utkarsh"
           << "\n";
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int t;
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}
