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.util.*;
import java.lang.*;
import java.io.*;

public class test
{
    public static int primeFactors(int n) 
    {
        int cnt = 0;
        while (n%2==0) 
        { 
            n /= 2; 
        }
        for (int i = 3; i <= Math.sqrt(n); i+= 2) 
        { 
            while (n%i == 0) 
            { 
                if (i%2==1)
                cnt++;
                n /= i; 
            } 
        } 
        if (n > 2 && n%2==1) 
            cnt++;

        return cnt;
    } 

    public static boolean is_prime(int n)
    {
        for (int i = 2; i <= Math.sqrt(n); i++) { 
        if (n % i == 0) { 
            return false;
        }
        }
        return true;
    }

	public static void main (String[] args) throws java.lang.Exception
	{
		inputs in=new inputs (System.in);
		int t = in.nextInt();
		while(--t>=0)
		{
			int n =in.nextInt();
            
            if (n==1)
            System.out.println("FastestFinger");
            else if (n==2)
            System.out.println("Ashishgup");
            else if (n%2==1)
            System.out.println("Ashishgup");
            else{
                int cnt = primeFactors(n);
                if (cnt==0 || (cnt==1 && (n/2)%2==1 && is_prime(n/2) ))
                System.out.println("FastestFinger");
                else
                System.out.println("Ashishgup");
                // int nos = n;
                // String ans = "FastestFinger";
                // int div = printDivisors(nos);
                // System.out.println(div);
                // while(div!=-1 && nos>1)
                // {
                //     System.out.println("Inside "+div);
                //     nos = nos/div;
                //     if (ans.equals("FastestFinger"))
                //     ans = "Ashishgup";
                //     else
                //     ans = "FastestFinger";
                //     div = printDivisors(nos);
                // }

                // if (nos>1)
                // {
                //     if (nos%2==0 && nos!=2)
                //     {
                //         System.out.println(ans);
                //     }
                //     else
                //     {
                //         if (ans.equals("FastestFinger"))
                //         ans = "Ashishgup";
                //         else
                //         ans = "FastestFinger";
                //         System.out.println(ans);
                //     }
                    
                // }
                // else
                // {
                //     System.out.println(ans);
                // }
                
            }
            

		}
        
		
	}
}

class inputs
{
    public BufferedReader reader;
    public StringTokenizer token;

    inputs(InputStream str)
    {
        reader=new BufferedReader(new InputStreamReader(str));
        token=null;
    }

    int nextInt()
    {
        while(token==null||!token.hasMoreTokens())
        {
            try { token=new StringTokenizer(reader.readLine());   }
            catch(IOException e){  throw new RuntimeException(e); }
        }
        return Integer.parseInt(token.nextToken());
    }

    long nextLong()
    {
        while(token==null||!token.hasMoreTokens())
        {
            try { token=new StringTokenizer(reader.readLine());   }
            catch(IOException e){  throw new RuntimeException(e); }
        }
        return Long.parseLong(token.nextToken());
    }

    String next()
    {
        while(token==null||!token.hasMoreTokens())
        {
            try { token=new StringTokenizer(reader.readLine());   }
            catch(IOException e){  throw new RuntimeException(e); }
        }
        return token.nextToken();
    }

}