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.io.*;
import java.util.*;

//int overflow in multiplication
//array index out-of-bound
//edge-cases

public class Main{
	
	static int mod=(int)1e9+7;
	
	public static void main(String[] args) throws IOException {
		Writer out=new Writer(System.out);
		Reader in=new Reader(System.in);
		int ts=in.nextInt();;
		outer: while(ts-->0) {
			
			long d=in.nextLong();
			long k=in.nextLong();
			int max=Integer.MIN_VALUE;
			for(int i=0; i*k<=d; i++) {
				int y=sqrt(d,(i*k),k);
				max=max(y+i,max);
			}
			if(max%2==0) out.println("Utkarsh");
			else out.println("Ashish");
			
			
		}
		out.close();		
	}

	static int sqrt(long d, long i, long k) {
		
		int t=0; int h=(int)(d/k);
		int tar=0;
		for(t=h; t>=1; t/=2) {
			
			while(t+h<=d && sqr(k*(tar+t))<=d*d-i*i) tar+=t;
			
		}
		return tar;
		
	}
	
	static long sqr(long n) {
		return n*n;
	}
/*********************************** UTILITY CODE BELOW **************************************/	
	static int abs(int a) {
		return a>0 ? a : -a;
	}
	static int max(int a, int b) {
		return a>b ? a : b;
	}
	static long max(long a, long b) {
		return a>b ? a : b;
	}
	static long min(long a, long b) {
		return a<b ? a : b;
	}
	static int min(int a, int b) {
		return a<b ? a : b;
	}
	static long pow(long n, long m) {
		if(m==0) return 1;
		long temp=pow(n,m/2);
		long res=temp*temp;
		if(m%2==0) return res;
		return res*n;
	}
	static void sort(int a[]) {
		List<Integer> al=new ArrayList<>();
		for(int i: a) al.add(i);
		Collections.sort(al);
		for(int i=0; i<a.length; i++) a[i]=al.get(i);
	}
	static class Pair{
		int u, v;
		Pair(int u, int v){this.u=u; this.v=v;}
		void sort(Pair[] coll) {
			List<Pair> al=new ArrayList<>();
			for(Pair p: coll) al.add(p);
			Collections.sort(al,new Comparator<Pair>() {
				public int compare(Pair o1, Pair o2) {
					if(o1.u==o2.u) return o1.v-o2.v;
					return o1.u-o2.u;
				}
			});
		}		
	}
	static class Reader{
		
		BufferedReader br;
		StringTokenizer to;
		
		Reader(InputStream stream){
			br=new BufferedReader(new InputStreamReader(stream));
			to=new StringTokenizer("");
		}
		String next() {
			while(!to.hasMoreTokens()) {
				try {
					to=new StringTokenizer(br.readLine());	
				}catch(IOException e) {}
				
			}
			return to.nextToken();
			
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
		long nextLong() {
			return Long.parseLong(next());
		}
		double nextDouble() {
			return Double.parseDouble(next());
		}
		int [] readArray(int n) {
			int a[]=new int[n];
			for(int i=0; i<n; i++) a[i]=nextInt();
			return a;
		}
		long [] readLongArray(int n) {
			long a[]=new long[n];
			for(int i=0; i<n ;i++) a[i]=nextLong();
			return a;
		}
		double[] readDoubleArray(int n) {
			double a[]=new double[n];
			for(int i=0; i<n; i++) a[i]=nextDouble();
			return a;
		}
	}
	static class Writer extends PrintWriter{
		Writer(OutputStream stream){
			super(stream);
		}
		void println(int [] array) {
			for(int i=0; i<array.length; i++) {
				print(array[i]+" ");
			}
			println();
		}
		void println(long [] array) {
			for(int i=0; i<array.length; i++) {
				print(array[i]+" ");
			}
			println();
		}
	}
	
}