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.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;



public class TaskD {

    public static void main(String[] arg) {
        final FastScanner in = new FastScanner(System.in);
        final PrintWriter out = new PrintWriter(System.out);
        final int T = in.nextInt();
        for(int t=0;t<T;t++){
          final int  d = in.nextInt();
          final int  k = in.nextInt();
          boolean ashish = true;
          long x = 0;
          final long y = 0;
          while(x*x<=(2L*d*d)){
              x+=k;
              ashish^=true;
          }
          out.println(ashish?"Ashish":"Utkarsh");
          // out.println(bfs(d,k));
        }
        out.close();
        in.close();
    }


    public static String bfs(final int d, final int k){
        //0 - ashish move
        //1 - utkash move
        int [][] moves = new int[][]{{k,0}, {0,k}};
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{0,0,0});
        boolean [][] visited = new boolean[d+1][d+1];
        visited[0][0]=true;
        int [] loosers = new int[2];
        while (!q.isEmpty()){
            int [] move = q.poll();
            int next = move[0]+1;
            next%=2;
            int outMoves = 0;
            for(int []m:moves){
                int x = move[1]+m[0];
                int y = move[2]+m[1];
                if(!isValid(d,x,y)){
                    outMoves++;
                    continue;
                }
                if(visited[x][y]==true){
                    continue;
                }
                visited[x][y]=true;
                q.add(new int[]{next, x, y});
            }
            if(outMoves==2){
                loosers[next]++;
            }
        }
        if(loosers[0]<loosers[1]){
            return "Utkarsh";
        }
        return "Ashish";
    }

    private static boolean isValid(long d, long x, long y){
        return d*d>=x*x+y*y;
    }


    private static class FastScanner {
        BufferedReader br;
        StringTokenizer st;

        FastScanner(InputStream stream) {
            try {
                br = new BufferedReader(new InputStreamReader(stream));
            } catch (Exception e) {
                e.printStackTrace();
            }
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

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

        int [] readIntArr(int n){
            int [] result = new int[n];
            for(int i=0;i<n;i++){
                result[i]=Integer.parseInt(next());
            }
            return result;
        }

        void close(){
            try {
                br.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }

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

    }

}