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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class code6 {

	public static void main(String[] args) throws CloneNotSupportedException {
		// TODO Auto-generated method stub
		FastReader scn = new FastReader();
		PrintWriter out = new PrintWriter(System.out);
		int t = scn.nextInt();
		//int p = t;
		while(t-->0) {
			 int n = scn.nextInt();
			 if(n == 1) {
				 out.println("FastestFinger");
				 continue;
			 }
			 if(n%2 == 1 || n==2) {
				 out.println("Ashishgup");
				 continue;
			 }
			 int k = 0;
			 while(n%2 == 0) {
				 n/=2;
				 k++;
			 }
			 int a1 = 0;
			 for(int i=1; i*i<=n; i++) {
				 if(n%i == 0) {
					 if(i != 1)
						 a1++;
					 if((n/i)%2 == 1 && n/i != i)
						 a1++;
				 }
			 }
			 if(k>1 && a1>=1) {
				 out.println("Ashishgup");
				 continue;
			 }
			 if(k==1) {
				 if(a1>1) {
					 out.println("Ashishgup");
				 }else
					 out.println("FastestFinger");
					 continue;
			 }
			 if(a1 == 0) {
				 out.println("FastestFinger");
				 continue;
			 }
			
		}
		out.flush();
	}
    static int c = 0 ;
	private static void dfs(char[][] arr, int i, int j) {
			if(i<0 || j<0 || i>=arr.length || j>=arr[0].length || arr[i][j]=='#'|| arr[i][j]=='B') {
				return;
			}
			if(arr[i][j]=='G') {
				c++;
			}
			arr[i][j]='#';
			dfs(arr , i+1 ,j );
			dfs(arr , i-1 ,j );
			dfs(arr , i ,j+1 );
			dfs(arr , i,j-1 );
			
	}

	public static void bfs (ArrayList<Integer>[] graph, int[] arr, int n, int i) {
		LinkedList<Integer> q = new LinkedList<>();
		//boolean[] vis = new boolean[n];
		for(int j=0; j<n; j++)
			arr[j] = Integer.MAX_VALUE;
		arr[i] = 0;
		q.addLast(i);
		while(!q.isEmpty()) {
			int u = q.removeFirst();
			//vis[u] = true;
			for(int j=0; j<graph[u].size(); j++) {
				if(arr[graph[u].get(j)] == Integer.MAX_VALUE) {
					arr[graph[u].get(j)] = arr[u]+1;
					q.addLast(graph[u].get(j));
				}
			}
		}
	}
	
	public static int first(ArrayList<Integer> arr, int low, int high, int x) 
    { 
        if(high >= low) 
        { 
            int mid = low + (high - low)/2; 
            if( ( mid == 0 || x > arr.get(mid-1)) && arr.get(mid) == x) 
                return mid; 
             else if(x > arr.get(mid)) 
                return first(arr, (mid + 1), high, x); 
            else
                return first(arr, low, (mid -1), x); 
        } 
    return -1; 
    } 
	static int gcd(int a, int b) 
    { 
    if (a == 0) 
        return b;  
    return gcd(b % a, a);  
    } 
      
	//public static int 
    static int lcm(int a, int b) 
    { 
        return (a*b)/gcd(a, b); 
    } 
    
    static class FastReader {
		BufferedReader br;
		StringTokenizer st;

		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

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

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

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

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

		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (IOException e) {
				e.printStackTrace();
			}
			return str;
		}
	}
}

