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>
import java.util.*;
import java.io.*;
public class Main
{
    public static void main(String[] args) throws Exception
	{
	    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	    PrintWriter pw=new PrintWriter(System.out);
	    int t=Integer.parseInt(br.readLine());
	    while(t-->0)
	    {
	        String s[]=(br.readLine()).split(" ");
	        int d=Integer.parseInt(s[0]);
	        int k=Integer.parseInt(s[1]);
	        int l=(d/k);
	        int a1[]=new int[l+1];
	        int a2[]=new int[l+1];
	        for(int i=0;i<=l;i++)
	        {
	            int temp=d*d-(k*i*k*i);
	            temp=(int)(Math.sqrt(temp));
	            temp/=k;
	            a1[i]=i;
	            a2[i]=temp;
	        }
	        int valid[]=new int[l+1];//-1 is invalid
	        for(int i=0;i<=l;i++)
	        {
	            if(valid[i]==-1)
	            {
	                continue;
	            }
	            if(a2[a2[i]]>a1[i])
	            {
	                valid[i]=-1;
	            }
	            
	        }
	        int nx0=1000000;
	        int ny0=1000000;
	        int nx1=1000000;
	        int ny1=1000000;
	        int nx2=1000000;
	        int ny2=1000000;
	        boolean found=false;
	        for(int i=0;i<=l;i++)
	        {
	            if(valid[i]==-1)
	            {
	                continue;
	            }
	            if(a1[i]==a2[i])
	            {
	                if((a1[i]+a2[i])<(nx0+ny0))
	                {
	                    nx0=a1[i];
	                    ny0=a2[i];
	                }
	                found=true;
	                
	            }
	            else if(((a1[i]-a2[i])==1) || ((a1[i]-a2[i])==-1))
	            {
	                if((a1[i]+a2[i])<(nx1+ny1))
	                {
	                    nx1=a1[i];
	                    ny1=a2[i];
	                }
	                found=true;
	            }
	            else if(((a1[i]-a2[i])==2) || ((a1[i]-a2[i])==-2))
	            {
	                if((a1[i]+a2[i])<nx2+ny2)
	                {
	                    nx2=a1[i];
	                    ny2=a2[i];
	                }
	                found=true;
	            }
	        }
	        if(found)
	        {
	            if(((nx1+ny1)<(nx0+ny0)) && ((nx1+ny1)<(nx2+ny2)))
	            {
	                pw.println("Ashish");
	            }
	            else
	            {
	                pw.println("Utkarsh");
	            }
	        }
	        else
	        {
	            int min=Integer.MAX_VALUE;
	            for(int i=0;i<=l;i++)
	            {
	                if(valid[i]==-1)
	                {
	                    continue;
	                }
	                if((a1[i]+a2[i])<min)
	                {
	                    min=a1[i]+a2[i];
	                }
	            }
	            if(min%2==1)
	            {
	                pw.println("Ashsish");
	            }
	            else
	            {
	                pw.println("Utkarsh");
	            }
	        }
	    }
	    pw.flush();
	}
	    
	
}
