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>
long long p = 1000000007;
using namespace std;
long long sq(long long i) { return i * i; }
long long fact(long n) {
  long ans = 1;
  for (long i = 1; i <= n; i++) ans = (ans * i) % p;
  return ans;
}
unsigned long long power(unsigned long long x, long y) {
  unsigned long long res = 1;
  x = x % p;
  while (y > 0) {
    if (y & 1) res = (res * x) % p;
    y = y >> 1;
    x = (x * x) % p;
  }
  return res;
}
long long modInverse(unsigned long long n, unsigned long long p) {
  return power(n, p - 2);
}
long long nCrModPFermat(unsigned long long n, unsigned long long r,
                        long long fac[]) {
  if (n < r) return 0;
  if (r == 0) return 1;
  return (fac[n] * modInverse(fac[r], p) % p * modInverse(fac[n - r], p) % p) %
         p;
}
void dfs(vector<long> v[], vector<long> &df, long cov[], long i) {
  df.push_back(i);
  for (long j = 0; j < v[i].size(); j++) {
    if (cov[v[i][j]] == 0) {
      cov[v[i][j]] = cov[i];
      dfs(v, df, cov, v[i][j]);
    }
  }
}
void djikstra(vector<pair<long, long>> v[], long d[], long par[], long s,
              long n) {
  for (long i = 0; i < n; i++) {
    d[i] = 1000000001;
    par[i] = -1;
  }
  par[s] = s;
  d[s] = 0;
  bool cov[n];
  for (long i = 0; i < n; i++) cov[i] = 0;
  long u = -1;
  for (int j = 0; j < n; j++) {
    u = -1;
    for (long i = 0; i < n; i++) {
      if (!cov[i] && (d[i] < d[u] || u == -1)) u = i;
    }
    cov[u] = 1;
    for (long i = 0; i < v[u].size(); i++) {
      if (d[v[u][i].first] > d[u] + v[u][i].second) {
        d[v[u][i].first] = d[u] + v[u][i].second;
        par[v[u][i].first] = u;
      }
    }
  }
}
long bfs(vector<long> v[], long par[], long root, long finish, long n) {
  long cov[n];
  for (long i = 0; i < n; i++) cov[i] = 0;
  queue<long> q;
  cov[root] = 0;
  q.push(root);
  while (!q.empty()) {
    for (long i = 0; i < v[q.front()].size(); i++) {
      if (cov[v[q.front()][i]] == 0) {
        q.push(v[q.front()][i]);
        cov[v[q.front()][i]] = cov[q.front()] + 1;
        par[v[q.front()][i]] = q.front();
      }
      if (v[q.front()][i] == finish) return cov[v[q.front()][i]];
    }
    q.pop();
  }
  return -1;
}
long findConnComp(vector<long> v[], long cov[], long n) {
  long j = 0;
  vector<long> df;
  for (long i = 0; i < n; i++) cov[i] = 0;
  for (long i = 0; i < n; i++) {
    if (!cov[i]) {
      cov[i] = ++j;
      dfs(v, df, cov, i);
    }
  }
  return j;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long t;
  cin >> t;
  while (t--) {
    long d, k;
    cin >> d >> k;
    long y = d / sqrt(2);
    y = k * (y / k);
    if (y * y + (y + k) * (y + k) > d * d)
      cout << "Utkarsh\n";
    else
      cout << "Ashish\n";
  }
}
