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<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<math.h>
#include<stack>
#include<queue>
#include<set>
#include<map>
using namespace std;

#define ll long long
#define vi vector<int>
#define vs vector<string>
#define vc vector<char>
#define twv vector<vector<int>>
#define fo(i,a,n) for(int i=int(a);i<int(n);i++)
#define op(x) cout<<x
#define ip(x) cin>>x
#define si set<int>
#define sc set<char>
#define ss set<string>
#define qqi queue<int>
#define qqc queue<char>
#define sti stack<int>
#define stc stack<char>
#define nl cout<<"\n"
#define pb(x) push_back(x)

int main()
{
	ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
    int test;ip(test);
    while(test--){
        ll int n,k;ip(n);ip(k);
        ll int q=1LL*n*n;int ans=0;int w=0;
        for(int i=1;i<q;i++){
            ll int x=k*i;
            ll int b=0;
            if(x%2!=0)b++;
            ll int a=x/2;
            ll int p=a%k;
            b+=a+p;
            a-=p;
            ll int z=b*b+a*a;
            if(z==q)w=1;
            if(z>=q){ans=i;break;}
        }
        if(ans%2!=0){
            if(w==0)cout<<"Utkarsh";
            else cout<<"Ashish";
        }
        else{
            if(w==1)cout<<"Utkarsh";
            else cout<<"Ashish";           
        }
        nl;
    }
	return 0;
}