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 io
import os

from collections import Counter, defaultdict, deque


def solveBrute(D, K):
    def inCircle(x, y):
        return x * x + y * y <= D * D

    if D > 30:
        return

    from functools import lru_cache

    @lru_cache(maxsize=None)
    def dp(r, c):
        if not inCircle(r + K, c) and not inCircle(r, c + K):
            return 1  # next player wins

        if not inCircle(r + K, c):
            return dp(r, c + K) ^ 1
        if not inCircle(r, c + K):
            return dp(r + K, c) ^ 1

        if dp(r + K, c) == 1 or dp(r, c + K) == 1:
            return 0
        return 1

    if True:
        print(D, K)
        for r in range(0, D + 1, K):
            print(
                "".join(
                    "01"[dp(r, c)] if abs(r - c) <= 2 else " "
                    for c in range(0, D + 1, K)
                )
            )

    return ["Ashish", "Utkarsh"][dp(0, 0)]


def solve(D, K):
    root = 0

    for s in range(K, D, K):
        if s * s + s * s <= D * D:
            root = s
        else:
            break

    assert 2 * (root ** 2) <= D * D < 2 * (root + K) ** 2

    player = 1
    if (root + K) * (root + K) + root * root <= D * D:
        player = 0

    return ["Ashish", "Utkarsh"][player]


DEBUG = False
if DEBUG:
    import random

    random.seed(0)
    for D in range(1, 30):
        for K in range(1, 10):

            ans1 = solveBrute(D, K)
            ans2 = solve(D, K)
            print(ans1, ans2)
            assert ans1 == ans2
    exit()

if __name__ == "__main__":
    input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

    TC = int(input())
    for tc in range(1, TC + 1):
        D, K = [int(x) for x in input().split()]
        ans = solve(D, K)
        print(ans)

