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.Closeable;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.OutputStreamWriter;
import java.io.UncheckedIOException;
import java.io.Writer;


public class D {
	public static void main(String[] args) {
		FastInput sc=new FastInput(System.in);
		int t=sc.readInt();
		while(t-->0){
			double d=sc.readInt();
			int k=sc.readInt();
			long x=(long)(d/(Math.sqrt(2)*k));
			long y=(long)(Math.sqrt(d*d-x*k*x*k)/k);
			System.out.println((x+y)%2==1?"Ashish":"Utkarsh");
		}
	}
	static class FastInput {
		private final InputStream is;
		private StringBuilder sB = new StringBuilder(1 << 13);
		private byte[] buf = new byte[1 << 13];
		private int bufLen;
		private int bufOffset;
		private int next;

		public FastInput(InputStream is) {
			this.is = is;
		}

		private int read() {
			while (bufLen == bufOffset) {
				bufOffset = 0;
				try {
					bufLen = is.read(buf);
				} catch (IOException e) {
					bufLen = -1;
				}
				if (bufLen == -1) {
					return -1;
				}
			}
			return buf[bufOffset++];
		}

		public void skipBlank() {
			while (next >= 0 && next <= 32) {
				next = read();
			}
		}

		public int readInt() {
			int sign = 1;
			skipBlank();
			if (next == '+' || next == '-') {
				sign = next == '+' ? 1 : -1;
				next = read();
			}
			int val = 0;
			if (sign == 1) {
				while (next >= '0' && next <= '9') {
					val = val * 10 + next - '0';
					next = read();
				}
			} else {
				while (next >= '0' && next <= '9') {
					val = val * 10 - next + '0';
					next = read();
				}
			}
			return val;
		}
		
		public String readString(StringBuilder builder) {
			skipBlank();
			while (next > 32) {
				builder.append((char) next);
				next = read();
			}
			return builder.toString();
		}

		public String next() {
			sB.setLength(0);
			return readString(sB);
		}
	}

	static class FastOutput implements AutoCloseable, Closeable, Appendable {
		private static final int THRESHOLD = 1 << 13;
		private final Writer os;
		private StringBuilder cache = new StringBuilder(THRESHOLD * 2);

		public FastOutput append(CharSequence csq) {
			cache.append(csq);
			return this;
		}

		public FastOutput append(CharSequence csq, int start, int end) {
			cache.append(csq, start, end);
			return this;
		}

		private void afterWrite() {
			if (cache.length() < THRESHOLD) {
				return;
			}
			flush();
		}

		public FastOutput(Writer os) {
			this.os = os;
		}

		public FastOutput(OutputStream os) {
			this(new OutputStreamWriter(os));
		}

		public FastOutput append(char c) {
			cache.append(c);
			afterWrite();
			return this;
		}

		public FastOutput append(int c) {
			cache.append(c);
			afterWrite();
			return this;
		}

		public FastOutput append(String c) {
			cache.append(c);
			afterWrite();
			return this;
		}

		public FastOutput println(int c) {
			return append(c).println();
		}

		public FastOutput println() {
			return append(System.lineSeparator());
		}

		public FastOutput flush() {
			try {
				os.append(cache);
				os.flush();
				cache.setLength(0);
			} catch (IOException e) {
				throw new UncheckedIOException(e);
			}
			return this;
		}

		public void close() {
			flush();
			try {
				os.close();
			} catch (IOException e) {
				throw new UncheckedIOException(e);
			}
		}
		public String toString() {
			return cache.toString();
		}
	}
}
