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.Scanner;

public class NumberGame 
{

	public static void main(String[] args) 
	{
		Scanner scan=new Scanner(System.in);
		int test=scan.nextInt();
		while(test-->0) 
		{
		
		int input=scan.nextInt();
		
		if(input<2) 
		{
			System.out.println("FastestFinger");
		}
		else if(input%2!=0) 
		{
			System.out.println("Ashishgup");
		}
		else //even number 
		{
			//if(getOddDivisor(input)==-1)//even number with no odd factors in it.
			if(isPowOf2(input)) 
			{
				if(input==2) 
				{
					
					System.out.println("Ashishgup");
				}
				else 
				{
				 System.out.println("FastestFinger");
				 }
			 }
			else if (input%4==0) //multiple even factors and one or more odd factors
			{
				System.out.println("Ashishgup");
			}
			else if(chkPrime(input/2))//odd factor= primenumber (1)
			 {
				System.out.println("FastestFinger");
			 }
			else //multiple odd factors and 1 even factor
			{
				System.out.println("Ashishgup");
			}
		 }
		}
		scan.close();
	}
	static boolean chkPrime(long input) 
	 {
		for(int i=3;i*i<=input;i++) 
		{
			if(input%i==0) 
			{
				return false;
			}
		}
		return true;
	 }
	/*static long getOddDivisor(long num) 
	{
		for(long i=3;i<=num/2;i++)
		{
		 if(i%2!=0) 
		 { 
			 if(num%i==0) 
			 {
			  return i;
			 }
		 }
		}
		return -1;
	}*/
	static boolean isPowOf2(long n) 
	{
		return n!=0 && ((n&(n-1)) == 0);
	}
}