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;
bool CustomCompare(const pair<long long int, long long int> &,
                   const pair<long long int, long long int> &);
long long int modmul(long long int, long long int);
long long int modadd(long long int, long long int);
long long int modsub(long long int, long long int);
template <class L, class R>
ostream &operator<<(ostream &os, pair<L, R> P);
template <class T>
ostream &operator<<(ostream &os, vector<T> V);
template <class T>
ostream &operator<<(ostream &os, set<T> second);
template <class T>
ostream &operator<<(ostream &os, unordered_set<T> second);
template <class T, class T1>
ostream &operator<<(ostream &os, map<T, T1> second);
template <class T, class T1>
ostream &operator<<(ostream &os, unordered_map<T, T1> second);
int isprime(long long int n) {
  for (int i = 2; i < sqrt(n) + 1; i++) {
    if (n % i == 0) return 0;
  }
  return 1;
}
void solve() {
  int d, k;
  cin >> d >> k;
  long long int div2 = (d * d) / (k * k);
  long long int curx = 0, cury = 0;
  long long int i = 1;
  long long int flag = 0;
  while (true) {
    curx = i * i;
    long long int z = div2 - curx - cury;
    if (z < 0) {
      flag = 1;
    }
    cury = i * i;
    z = div2 - curx - cury;
    if (z < 0) break;
    i++;
  }
  if (flag) {
    cout << "Utkarsh\n";
  } else {
    cout << "Ashish\n";
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  ;
  vector<long long int> a(1e5);
  for (int i = 0; i < 1e5; i++)
    ;
  int t = 1;
  cin >> t;
  int i = 1;
  while (i <= t) {
    solve();
    i++;
  }
  return 0;
}
template <class L, class R>
ostream &operator<<(ostream &os, pair<L, R> P) {
  return os << "(" << P.first << ", " << P.second << ")";
}
template <class T>
ostream &operator<<(ostream &os, vector<T> V) {
  if (V.size()) {
    os << "[" << V[0];
    for (int i = 1; i < V.size(); i++) os << ", " << V[i];
    return os << "]";
  }
  return os << "[]";
}
template <class T>
ostream &operator<<(ostream &os, set<T> second) {
  os << "{";
  for (auto s : second) os << s << ", ";
  return os << "}";
}
template <class T>
ostream &operator<<(ostream &os, unordered_set<T> second) {
  os << "{";
  for (auto s : second) os << s << ", ";
  return os << "}";
}
template <class T, class T1>
ostream &operator<<(ostream &os, map<T, T1> second) {
  os << "{" << '\n';
  for (auto s : second)
    os << "\t" << s.first << " : " << s.second << "," << '\n';
  return os << "}" << '\n';
}
template <class T, class T1>
ostream &operator<<(ostream &os, unordered_map<T, T1> second) {
  os << "{" << '\n';
  for (auto s : second)
    os << "\t" << s.first << " : " << s.second << "," << '\n';
  return os << "}" << '\n';
}
bool CustomCompare(const pair<long long int, long long int> &i,
                   const pair<long long int, long long int> &j) {
  if (i.first == j.first) return i.second < j.second;
  return i.first < j.first;
}
long long int modmul(long long int a, long long int b) {
  long long int ret = (a % 1000000007) * (b % 1000000007);
  ret %= 1000000007;
  return ret;
}
long long int modadd(long long int a, long long int b) {
  long long int ret = (a % 1000000007) + (b % 1000000007);
  ret %= 1000000007;
  return ret;
}
long long int modsub(long long int a, long long int b) {
  a = a % 1000000007;
  b = b % 1000000007;
  if (a < b) a += 1000000007;
  long long int ret = a - b;
  ret %= 1000000007;
  return ret;
}
