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.*;

public class Main {
    static PrintWriter pw;
    static Scanner sc;
    static long ceildiv(long x, long y) { return (x+y-1)/y; }
    static int mod(long x, int m) { return (int)((x%m+m)%m); }
    static void put(TreeMap<Long, Integer> map, Long p){if(map.containsKey(p)) map.replace(p, map.get(p)+1); else map.put(p, 1); }
    static void rem(TreeMap<Long, Integer> map, Long p){ if(map.get(p)==1) map.remove(p);else map.replace(p, map.get(p)-1); }
    static void printf(double x, int dig){ String s="%."+dig+"f"; pw.printf(s, x); }
    static int Int(boolean x){ return x?1:0; }
    static final int inf=(int)1e9, mod=998244353;
    static final long infL=inf*1l*inf;
    static final double r2=Math.sqrt(2), eps=1e-9;
    public static long gcd(long x, long y) { return y==0? x: gcd(y, x%y); }
    public static void main(String[] args) throws IOException {
        sc=new Scanner(System.in);
        pw=new PrintWriter(System.out);
        int t= sc.nextInt();
        while(t-->0){
            int d=sc.nextInt(), k=sc.nextInt();
            int ans=solve(d, k);
            pw.println(ans%2==0?"Utkarsh":"Ashish");
        }
        pw.close();
    }
    static int solve(int d, int k){
        int st=0, end=d-d%k;
        while(end-st>=3*k){
            int diff=(end-st)/k;
            int m1=st+(diff/2)*k, m2=m1+k;
            int h1=(int)Math.sqrt(d*1l*d-m1*m1), h2=(int)Math.sqrt(d*1l*d-m2*1l*m2);
            h1-=h1%k; h2-=h2%k;
            long a=m1*1l*h1, b=m2*1l*h2;
            if(a>b){
                end=m2-k;
            }else if(a<b){
                st=m1+k;
            }else{
                st=m1;
                end=m2;
            }
        }
        int max=0;
        for(int i=st; i<=end; i+=k){
            int x=(int)Math.sqrt(d*1l*d-i*1l*i);
            x-=x%k;
            max=Math.max((i+x)/k, max);
        }
        return max;
    }
    static void printArr(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++)
            pw.print(arr[i] + " ");
        pw.println(arr[arr.length - 1]);
    }
    static void printArr(long[] arr) {
        for (int i = 0; i < arr.length - 1; i++)
            pw.print(arr[i] + " ");
        pw.println(arr[arr.length - 1]);
    }
    static void printArr(double[] arr) {
        for (int i = 0; i < arr.length - 1; i++)
            pw.print(arr[i] + " ");
        pw.println(arr[arr.length - 1]);
    }
    static void printArr(Integer[] arr) {
        for (int i = 0; i < arr.length; i++)
            pw.print(arr[i] + " ");
        pw.println();
    }
    static void printArr(ArrayList<Integer> list) {
        for (int i = 0; i < list.size(); i++)
            pw.print(list.get(i)+1+" ");
        pw.println();
    }
    static class Scanner {
        StringTokenizer st;
        BufferedReader br;
        public Scanner(InputStream s) {
            br = new BufferedReader(new InputStreamReader(s));
        }

        public Scanner(FileReader r) {
            br = new BufferedReader(r);
        }

        public String next() throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

        public int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        public long nextLong() throws IOException {
            return Long.parseLong(next());
        }

        public String nextLine() throws IOException {
            return br.readLine();
        }

        public double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }
        public int[] nextDigits() throws IOException{
            String s=nextLine();
            int[] arr=new int[s.length()];
            for(int i=0; i<arr.length; i++)
                arr[i]=s.charAt(i)-'0';
            return arr;
        }
        public int[] nextArr(int n) throws IOException {
            int[] arr = new int[n];
            for (int i = 0; i < arr.length; i++)
                arr[i] = nextInt();
            return arr;
        }
        public Integer[] nextsort(int n) throws IOException{
            Integer[] arr=new Integer[n];
            for(int i=0; i<n; i++)
                arr[i]=nextInt();
            return arr;
        }
        public Pair nextPair() throws IOException{
            return new Pair(nextInt(), nextInt());
        }
        public Pair[] nextPairArr(int n) throws IOException{
            Pair[] arr=new Pair[n];
            for(int i=0; i<n; i++)
                arr[i]=nextPair();
            return arr;
        }
        public boolean ready() throws IOException {
            return br.ready();
        }
    }
    static class Quad{
        int a, b, c, d;
        public Quad(int w, int x, int y, int z){
            a=w;
            b=x;
            c=y;
            d=z;
        }
        public int hashCode(){
            return (int)(a*1e9+b*1e6+c*1e3+d);
        }
        public boolean equals(Object o){
            if(o.getClass()!=this.getClass())
                return false;
            Quad q=(Quad)o;
            return a==q.a && b==q.b && c==q.c && d==q.d;
        }
        public String toString(){
            return a+" "+b+" "+c+" "+d;
        }
    }
    static class Pair implements Comparable<Pair>{
        int x;
        int y;
        public Pair(int x, int y) {
            this.x=x;
            this.y=y;
        }
        public boolean contains(int a){
            return x==a || y==a;
        }
        public int hashCode() {
            return (this.x*1000000000+this.y);
        }
        public int compareTo(Pair p){
            return y-p.y;
        }
        public boolean equals(Object obj) {
            if (obj == null) {
                return false;
            }
            if (this.getClass() != obj.getClass()) {
                return false;
            }
            Pair p = (Pair) obj;
            return this.x==p.x && this.y==p.y;
        }
        public Pair clone(){
            return new Pair(x, y);
        }
        public String toString(){
            return this.x+" "+this.y;
        }
        public void add(Pair p){
            x+=p.x;
            y+=p.y;
        }
    }
    static class LP implements Comparable<LP>{
        long x, y;
        public LP(long a, long b){
            x=a;
            y=b;
        }
        public void add(LP p){
            x+=p.x;
            y+=p.y;
        }
        public boolean equals(LP p){
            return p.x==x && y==p.y;
        }
        public String toString(){
            return this.x+" "+this.y;
        }
        public int compareTo(LP p){
            if(x>p.x)
                return 1;
            if(x<p.x)
                return -1;
            return Long.compare(y, p.y);
        }
    }
    static class Triple implements Comparable<Triple>{
        int x, y, z;
        public Triple(int a, int b, int c){
            x=a;
            y=b;
            z=c;
        }
        public int compareTo(Triple t){
            if(this.y!=t.y)
                return y-t.y;
            return x-t.x;
        }
        public String toString(){
            return x+" "+y+" "+z;
        }
    }
    static class Fenwick{
        long[] tree, arr;
        public Fenwick(long[] a){
            arr=a.clone();
            build();
        }
        public void build(){
            tree=new long[arr.length+1];
            for(int i=0; i<arr.length; i++)
                build(i+1);
        }
        public void build(int i){
            long val=arr[i-1];
            while(i<tree.length){
                tree[i]+=val;
                i+=i&(-i);
            }
        }
        public long query(int i, int j){
            return query(j)-query(i-1);
        }
        public long query(int i){
            if(i==0)
                return 0;
            return tree[i]+query(i-(i&-i));
        }
    }
}