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

public class D {
    public static void main(String[] args) throws IOException {
        Scanner scan = new Scanner(System.in);
//        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        int t = scan.nextInt();
        while (t-->0)
        {
//            int n= Integer.parseInt(br.readLine());
            int d= scan.nextInt();
            int k= scan.nextInt();
            long dd= d*d;
            int count=0;
            long x=0,y=0;
            for (int i=0;;i++){
                if (x*x+y*y>dd) break;
                x+=k;
                if (x*x+y*y>dd) break;
                else count++;
                y+=k;
                if (x*x+y*y>dd) break;
                else count++;
            }
            System.out.println(count);

            if (count%2==0) System.out.println("Utkarsh");
            else System.out.println("Ashish");
        }
    }

    static long nCr(int n, int r)
    {
        long p = 1, k = 1;
        if (n - r < r) {
            r = n - r;
        }
        if (r != 0) {
            while (r > 0) {
                p *= n;
                k *= r;
                long m = gcd(p, k);
                p /= m;
                k /= m;
                n--;
                r--;
            }
        } else {
            p = 1;
        }
        return p;
    }

    static long gcd(long n1, long n2) {
        long gcd = 1;
        for (int i = 1; i <= n1 && i <= n2; ++i) {
            if (n1 % i == 0 && n2 % i == 0) {
                gcd = i;
            }
        }
        return gcd;
    }

    static int factorial(int n)
    {
        int res[] = new int[500];
        res[0] = 1;
        int res_size = 1;
        for (int x = 2; x <= n; x++)
            res_size = multiply(x, res, res_size);

        for (int i=res_size-1;i>=0;i--)
            return (res[i]);
        return 1;
    }

    static int multiply(int x,int res[],int res_size)
    {
        int carry = 0; // Initialize carry
        for (int i=0;i<res_size;i++)
        {
            int prod = res[i] * x + carry;
            res[i] = prod % 10; // Store last digit of
            carry = prod/10; // Put rest in carry
        }
        while (carry!=0)
        {
            res[res_size] = carry % 10;
            carry = carry / 10;
            res_size++;
        }
        return res_size;
    }
}
