Ashishgup and FastestFinger play a game. 

They start with a number n and play in turns. In each turn, a player can make any one of the following moves:

  * Divide n by any of its odd divisors greater than 1. 
  * Subtract 1 from n if n is greater than 1. 



Divisors of a number include the number itself.

The player who is unable to make a move loses the game.

Ashishgup moves first. Determine the winner of the game if both of them play optimally.

Input

The first line contains a single integer t (1 ≤ t ≤ 100) — the number of test cases. The description of the test cases follows.

The only line of each test case contains a single integer — n (1 ≤ n ≤ 10^9).

Output

For each test case, print "Ashishgup" if he wins, and "FastestFinger" otherwise (without quotes).

Example

Input


7
1
2
3
4
5
6
12


Output


FastestFinger
Ashishgup
Ashishgup
FastestFinger
Ashishgup
FastestFinger
Ashishgup

Note

In the first test case, n = 1, Ashishgup cannot make a move. He loses.

In the second test case, n = 2, Ashishgup subtracts 1 on the first move. Now n = 1, FastestFinger cannot make a move, so he loses.

In the third test case, n = 3, Ashishgup divides by 3 on the first move. Now n = 1, FastestFinger cannot make a move, so he loses.

In the last test case, n = 12, Ashishgup divides it by 3. Now n = 4, FastestFinger is forced to subtract 1, and Ashishgup gets 3, so he wins by dividing it by 3.
import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.InputMismatchException;
public class C651 {

	static HashMap<Integer, Boolean> map;
	static HashSet<Integer> isPow2;
	
	public static void main(String[] args) {
		FastScanner in = new FastScanner(System.in);
		int T = in.nextInt();
		StringBuilder sb = new StringBuilder();
		
		map = new HashMap<>();
		isPow2 = new HashSet<>();
		
		for(int i = 0; i < 32; i++) {
			int temp = (1 << i);
			isPow2.add(temp);
		}
		
		while(T --> 0) {
			int N = in.nextInt();
			boolean b = isWin(N);
			
			if(b) {
				sb.append("Ashishgup\n");
			}
			else {
				sb.append("FastestFinger\n");
			}
			
		}
		
		System.out.print(sb);

	}
	
	public static boolean isWin(int N) {
		if(N == 1) {
			return false;
		}
		if(N == 2) {
			return true;
		}
		if(N % 2 == 1) {
			return true;
		}
		if(isPow2.contains(N)) {
			return false;
		}
		if(map.containsKey(N)) {
			return map.get(N);
		}
		
		ArrayList<Integer> oddDivisors = new ArrayList<>();
		
		for(int i = 2; i <= Math.sqrt(N); i++) {
			if(N % i == 0) {
				if(i % 2 == 1) {
					oddDivisors.add(i);
				}
				if((N/i) % 2 == 1) {
					if(i != N/i) {
						oddDivisors.add(N/i);
					}
				}
			}
		}
		
		//System.out.println("oddDivisors of " + N + " = " + oddDivisors);
		
		boolean childAllWin = true;
		
		for(int div : oddDivisors) {
			boolean b = isWin(N/div);
			
			if(!b) {
				childAllWin = false;
				break;
			}
		}
		
		if(childAllWin) {
			map.put(N, false);
		}
		else {
			map.put(N, true);
		}
		//map.put(N, childAllWin);
		
		
		return !childAllWin;
	}
	
	/**
	 * Source: Matt Fontaine
	 */
	static class FastScanner {
		private InputStream stream;
		private byte[] buf = new byte[1024];
		private int curChar;
		private int chars;

		public FastScanner(InputStream stream) {
			this.stream = stream;
		}

		int read() {
			if (chars == -1)
				throw new InputMismatchException();
			if (curChar >= chars) {
				curChar = 0;
				try {
					chars = stream.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (chars <= 0)
					return -1;
			}
			return buf[curChar++];
		}

		boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		boolean isEndline(int c) {
			return c == '\n' || c == '\r' || c == -1;
		}

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

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

		public double nextDouble() {
			return Double.parseDouble(next());
		}

		public String next() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		public String nextLine() {
			int c = read();
			while (isEndline(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isEndline(c));
			return res.toString();
		}
	}

}
/*
7
1
2
3
4
5
6
12
outputCopy
FastestFinger
Ashishgup
Ashishgup
FastestFinger
Ashishgup
FastestFinger
Ashishgup
*/