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.
/* package codechef; // don't place package name! */

import java.lang.*;
import java.io.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.*;
/* Name of the class has to be "Main" only if the class is public. */
public class Codechef
{
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
		FastReader sc = new FastReader();
		PrintWriter out = new PrintWriter(System.out);
		int  t= sc.nextInt();
		while(t-->0)
		{
		    int n = sc.nextInt();
		    if(n==1) {out.println("FastestFinger");continue;}
		    if(n%2!=0 || n==2)
		    {
		        out.println("Ashishgup");
		        continue;
		    }
		    
		    ArrayList<Integer> factors = new ArrayList<>();
		    for(int i=2;i<=(int)Math.sqrt(n);i++)
		    {
		        if(n%i==0)
		        {
		            if(i%2!=0) factors.add(i);
		            if((n/i)%2!=0) factors.add(n/i);
		        }
		    }
		    if(factors.size()==0) out.println("FastestFinger");
		    else if(factors.size()>1) out.println("Ashishgup");
		    else
		    {
		        if(n/factors.get(0)==2) out.println("FastestFinger");
		        else out.println("Ashishgup");
		    }
		}
		
		out.close();
	}
}

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; 
    } 
}